ALORA4 - Editorial

rkr_725 · January 23, 2019, 2:11pm

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;

Let n=k/3.
So we can clearly see that proper value of e will exist only if k is divisible by 3.

Observation 2:
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).

Observation 3:

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