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
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).
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.
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?
31.07.2022 18:53