For a positive integer $n$, consider a square cake which is divided into $n \times n$ pieces with at most one strawberry on each piece. We say that such a cake is delicious if both diagonals are fully occupied, and each row and each column has an odd number of strawberries. Find all positive integers $n$ such that there is an $n \times n$ delicious cake with exactly $\left\lceil\frac{n^2}{2}\right\rceil$ strawberries on it.
Problem
Source: 2021 Thailand TST 0.1
Tags: combinatorics, table, Team Selection Test
demmy
05.11.2022 15:35
Bump!!!!!!!
Quidditch
05.11.2022 17:52
The answer is $n\geq 5$, which can be done by induction $n\to n+2$ and casework when $n\equiv 0,1,2,3\pmod{4}$. I'm too lazy to write a sol now, but hopefully, I will add it later.
Quidditch
06.11.2022 07:03
The answer is $n\geq 5$ which we will prove it by induction $n\to n+2$ for odd $n$ and $n\to n+4$ for even $n$. First, we provide the construction of the base cases $n=5,6,8$. Here's $n=5$ construction. [asy][asy] size(3cm,0); defaultpen(fontsize(12pt)); int i; fill((0,0)--(0,2)--(2,2)--(2,1)--(1,1)--(1,0)--cycle,palered); fill((0,5)--(2,5)--(2,3)--(1,3)--(1,4)--(0,4)--cycle,palered); fill((2,3)--(3,3)--(3,2)--(2,2)--cycle,palered); fill((3,0)--(3,2)--(4,2)--(4,1)--(5,1)--(5,0)--cycle,palered); fill((5,5)--(5,3)--(3,3)--(3,4)--(4,4)--(4,5)--cycle,palered); for(i=0;i<=5;++i){ draw((i,0)--(i,5) ^^ (0,i)--(5,i)); } [/asy][/asy] Here's $n=6$ construction. [asy][asy] size(3cm,0); defaultpen(fontsize(12pt)); int i; fill((0,6)--(1,6)--(1,5)--(2,5)--(2,4)--(4,4)--(4,2)--(2,2)--(2,3)--(1,3)--(1,4)--(0,4)--cycle,palered); fill((4,6)--(6,6)--(6,5)--(5,5)--(5,4)--(4,4)--cycle,palered); fill((0,0)--(1,0)--(1,1)--(0,1)--cycle,palered); fill((1,1)--(3,1)--(3,2)--(1,2)--cycle,palered); fill((6,0)--(6,1)--(5,1)--(5,0)--cycle,palered); fill((3,0)--(3,1)--(4,1)--(4,0)--cycle,palered); fill((4,1)--(4,2)--(5,2)--(5,1)--cycle,palered); fill((5,2)--(5,3)--(6,3)--(6,2)--cycle,palered); for(i=0;i<=6;++i){ draw((i,0)--(i,6) ^^ (0,i)--(6,i)); } [/asy][/asy] Here's $n=8$ construction. [asy][asy] size(3cm,0); defaultpen(fontsize(12pt)); int i; fill((0,8)--(1,8)--(1,7)--(0,7)--cycle,palered); fill((0,3)--(1,3)--(1,2)--(0,2)--cycle,palered); fill((0,0)--(0,1)--(1,1)--(1,0)--cycle,palered); fill((1,3)--(1,7)--(2,7)--(2,3)--cycle,palered); fill((2,2)--(2,3)--(3,3)--(3,2)--cycle,palered); fill((1,1)--(1,2)--(5,2)--(5,1)--cycle,palered); fill((3,3)--(5,3)--(5,5)--(3,5)--cycle,palered); fill((2,5)--(3,5)--(3,6)--(2,6)--cycle,palered); fill((2,8)--(5,8)--(5,6)--(2,6)--cycle,palered); fill((5,0)--(5,1)--(6,1)--(6,0)--cycle,palered); fill((5,2)--(5,3)--(6,3)--(6,2)--cycle,palered); fill((5,5)--(5,6)--(6,6)--(6,5)--cycle,palered); fill((7,7)--(7,8)--(8,8)--(8,7)--cycle,palered); fill((7,3)--(7,4)--(8,4)--(8,3)--cycle,palered); fill((7,0)--(7,1)--(8,1)--(8,0)--cycle,palered); fill((6,6)--(6,7)--(7,7)--(7,6)--cycle,palered); fill((6,3)--(6,4)--(7,4)--(7,3)--cycle,palered); fill((6,1)--(6,2)--(7,2)--(7,1)--cycle,palered); for(i=0;i<=8;++i){ draw((i,0)--(i,8) ^^ (0,i)--(8,i)); } [/asy][/asy] Now, for inductive step, let the square in row $i$ column $j$ be $a_{i,j}$.