Iranian Mathematical Olympiad

First, we prove that $n=36$ is not enough. Assume that numbers $1,2,\dots ,36$ are assigned to the cells of the table with the described conditions. Since the number $2$ is used, so even numbers (i.e. $2,4,6,\dots ,36$) must be put in its row and its column. Similarly, the number $35$ is used, so we have to put odd numbers (i.e. $1,3,5,\dots ,35$) in its row and its column. But the intersection of the row containing $35$ and the column containing $2$ has to be odd and even at the same time. Contradiction!

Now it is sufficient to make an example with numbers $1,2,\dots ,37$. In this example, the even numbers are just in the first row, and the other cells are filled with appropriate numbers (just by shifting the odd numbers).

2	4	6	8	10	12	14	16	18	20	22	24	26	28	30	32	34	36
37	1	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33
35	37	1	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31
33	35	37	1	3	5	7	9	11	13	15	17	19	21	23	25	27	29
31	33	35	37	1	3	5	7	9	11	13	15	17	19	21	23	25	27
29	31	33	35	37	1	3	5	7	9	11	13	15	17	19	21	23	25
27	29	31	33	35	37	1	3	5	7	9	11	13	15	17	19	21	23
25	27	29	31	33	35	37	1	3	5	7	9	11	13	15	17	19	21
23	25	27	29	31	33	35	37	1	3	5	7	9	11	13	15	17	19
21	23	25	27	29	31	33	35	37	1	3	5	7	9	11	13	15	17
19	21	23	25	27	29	31	33	35	37	1	3	5	7	9	11	13	15
17	19	21	23	25	27	29	31	33	35	37	1	3	5	7	9	11	13
15	17	19	21	23	25	27	29	31	33	35	37	1	3	5	7	9	11
13	15	17	19	21	23	25	27	29	31	33	35	37	1	3	5	7	9
11	13	15	17	19	21	23	25	27	29	31	33	35	37	1	3	5	7
9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	1	3	5
7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	1	3
5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	1

Thus, the least possible value of $n$ is $37$.