Problem
Source: Belarusian National Olympiad 2021
Tags: combinatorics, number theory
31.12.2024 20:18
could you clarify what "spiral" way means? maybe provide a pic
31.12.2024 20:40
As the title says, next year
13.01.2025 08:35
nAalniaOMliO wrote: As the title says, next year I’ve been waiting for a year…
13.01.2025 18:26
RagvaloD wrote: Added example for $n=5$ in attachments So this implies $n$ is odd... Right? Or how could we construct a spiral pattern for $n$ even?
13.01.2025 19:35
BR1F1SZ wrote: RagvaloD wrote: Added example for $n=5$ in attachments So this implies $n$ is odd... Right? Or how could we construct a spiral pattern for $n$ even? | |־־־־| | | |־| | | |__| | | ____| this is the best spiral I managed to get, but this is what it's supposed to look like
13.01.2025 19:40
Which main diagonal?
13.01.2025 20:33
MrBlueLand wrote: BR1F1SZ wrote: RagvaloD wrote: Added example for $n=5$ in attachments So this implies $n$ is odd... Right? Or how could we construct a spiral pattern for $n$ even? | |־־־־| | | |־| | | |__| | | ____| this is the best spiral I managed to get, but this is what it's supposed to look like Great, thanks! Scilyse wrote: Which main diagonal? I guess it's the one that runs from the top-left corner to the bottom-right corner.
14.01.2025 23:55
RagvaloD wrote: Added example for $n=5$ in attachments Thanks to RagvaloD so much! I added the picture to the post.
15.01.2025 00:38
Only $3$. Incredibly it's a number theory problem and not a combinatoric problem. Coloring at chessboard $n$ must be odd. Now we prove that $n$ is prime. Start counting from the center insted the corner. The numbers that are non the diagonal are $(2x+1)^2$ for $x$ from $1$ to $(n+1)/2$ and $(2y)^2+1$ for $y$ from $1$ to $(n-1)/2$. Now if the first tipe of numbers are all different then the quadratico residue mod $n$ are at least $(n+1)/2$ so $n$ is prime. Now impose that $4x^2+1$ is not a quadratic residue. $1\equiv (y-2x)(y+2x)$ must have only solution $x=0$ and so $y=1$ or $y=-1$. But for $n\geq 5$ this equation has too mucho solutions.
15.01.2025 01:27
Great solution! Though you missed that $n=1$ also works.