Let $ m\geq n\geq 4$ be two integers. We call a $ m\times n$ board filled with 0's or 1's good if 1) not all the numbers on the board are 0 or 1; 2) the sum of all the numbers in $ 3\times 3$ sub-boards is the same; 3) the sum of all the numbers in $ 4\times 4$ sub-boards is the same. Find all $ m,n$ such that there exists a good $ m\times n$ board.
Problem
Source: Kazakhstan international contest 2006, Problem 3
Tags: combinatorics proposed, combinatorics
26.02.2006 14:54
I guess the conclution is : We can do it if n is not more than 5. We would finish the proof if we can show that: m=n=6 does not fit the condition
27.02.2006 14:40
the whole solution: [step1]We prove that 6*6 does not fit the condition. Calculate all the 3*3 and 4*4 in 6*6, There are 9 4*4s and 16 3*3s,each number in the board is calculated same times. But all the 3*3s are equal,all the 4*4s are equal. So the sum of 3*3s is divisible by 9 the sum of 4*4s is divisible by 16 Easy to know it is impossible. [step2]We can say n*6,$n\geq 6$ does not fit the condition because of Step1 [step3]We give an example of n*5 board $n\geq 5$ 1 1 1 1 1 1 1 1...... 1 1 1 1 1 1 1 1...... 0 0 0 0 0 0 0 0...... 1 1 1 1 1 1 1 1...... 1 1 1 1 1 1 1 1...... the example of n*4 can be found easy. So ,all the (m,n) is (4+m,4),(5+m,5) m is a natural number
11.06.2008 01:25
I cannot follow you in step 2.
11.10.2012 12:22
Sorry for reviving old topic . Could anyone post more simply solution please?
11.10.2012 12:24
There cannot be a more simple solution, as this is so simple itself (how much simpler would you like it to be?).