problem link : Goblet of Fire
Author : Ritesh Gupta
Tester : Shubham Gupta
Editorialist : Rajan Kumar Raj
Pre-Requisite : Number theory
Problem : You are given with a 3*3 matrix and a integer “k”. You have to find the number of matrices that
satisfies the given condition.
Sum of all the numbers in each row is equal to k
Sum of all the numbers in each column is equal to k
Sum of all the numbers in each diagonal is equal to k
All the numbers in the magic square are in the range of 1 to k (including both)
There should be at least 1 odd number in the matrix.
All the numbers need not be distinct.
Explanation : Let us observe step by step-
Observation 1: Let us consider the given matrix
. 1 2 3
1 a b c
2 d e f
3 g h i
Now as we know that sum of each column , row and diagonal is equal to k.
Therefore we make equations from diagonals and 2nd row and 2nd column.
We get: b+e+h=k d+e+f=k a+e+i=k c+e+g=k Now adding these equation and arranging in required way we get: (a+d+g)+(c+f+i)+(b+h+e)+3e=4k 3e=k e=k/3;
So we can clearly see that proper value of e will exist only if k is divisible by 3.
In this observation we are first not considering the condition that 1 element of a matrix must be an odd number.
Now let us make a matrix in which value of k is divisible by 3.
. 1 2 3
1 1 x _
2 _ e _
3 _ _ _
Now we know that sum of diagonal is k.
If we make equation and try to find value of x then it will lie between 2n-2 and 2n ,i.e., we will get 1 value.
If we update the value of A(1)(1) to 2 then we will get 3 values after solving the equation.
Similarily till n it will increase to 2n-1 and then it will start decreasing till it reaches 1.
So the series will be like 1 3 5 . . . . . 2n-3 2n-1 2n-1 . . . . 5 3 1
So our required answer will be n^2+(n-1)^2.
Let us denote our obtained answer by G(k).
Now let us see the case where an odd number must exist in the matrix.
In this case the required answer will be G(k)-G(k/2).
This part is left for user interpretation.
Time Complexity : O(1)
Setter Solution :Click here