Find the smallest positive integer $n$ such that we can write numbers $1,2,\dots ,n$ in a 18*18 board such that: i)each number appears at least once ii)In each row or column,there are no two numbers having difference 0 or 1
Problem
Source: 2018 Iran national olympiad third round combinatorics exam
Tags: combinatorics
Taha1381
29.08.2018 14:55
It's easy to show the minimum is biiger than $35$and build a grid for $37$.But I can't figure out what the answer is BTW constructing an example for $36$seems to be impossible(or difficult).
Etemadi
30.08.2018 12:01
The answer is 37. To disprove 36, just note that the row consisting number 2, can only contain even numbers; and the column consisting 35 can only contain odds. These two conflict. Constructing an example for 37 isn't hard.
Tung-CHL
18.11.2020 08:04
Etemadi wrote: The answer is 37. To disprove 36, just note that the row consisting number 2, can only contain even numbers; and the column consisting 35 can only contain odds. These two conflict. Constructing an example for 37 isn't hard. How do you construct the example of 37?
Mehrshad
31.07.2022 18:53
[asy][asy]
size(350);
int a;
string s;
for(int i=0;i<=18;++i){
draw((i,0)--(i,-18));
draw((0,-i)--(18,-i));
}
for(int i=1;i<=18;++i){
for(int j=1;j<=18;++j){
if(i<=j) a=2*(j-i)+1;
else a=39-2*(i-j);
if(j==18) ++a;
s=(string)a;
label((j-0.5,-i+0.5),s);
}
}
[/asy][/asy]