An $n\times n$ square table is divided into $n^2$ unit cells. Some unit segments of the obtained grid (i.e. the side of any unit cell) is colored black so that any unit cell of the given square has exactly one black side. Find a) the smallest b) the greatest possible number of black unit segments.
Problem
Source: 2017 Belarus Team Selection Test 1.2
Tags: combinatorics, Boards
leibnitz
11.05.2019 18:52
A(most probably wrong)
b)for maximum IDK.
a)for minimum if n is odd then $\frac{n^{2}+1}{2}$
if even then $\frac{n^{2}}{2}$.
leibnitz
11.05.2019 19:00
Can anyone verify my answers?
ComiCabE
03.06.2019 12:49
Let $b$ and $i$ be the numbers of segments colored on the boundary and inside the grid respectively. Clearly $b+2i=n^2$. a) (i) $n$ is odd. Then $b$ is odd as well, and therefore $b \ge 1$, so $$b+i \ge 1+\frac{n^2-1}{2}=\frac{n^2+1}{2}$$(ii) $n$ is even. $$b+i \ge \frac{n^2}{2}$$b) (i) $n$ is odd. Then $b$ is odd as well, and therefore $b \le 4(n-1)-1$, so $$b+i \le 4(n-1)-1+\frac{n^2-(4(n-1)-1)}{2}=\frac{n^2+4n-5}{2}$$(ii) $n$ is even. Then $b \le 4(n-1)$, so $$b+i \le 4(n-1)+\frac{n^2-4(n-1)}{2}=\frac{n^2+4n-4}{2}$$All four values are clearly attainable.
prof.
04.06.2019 08:13
Where we can find more Problems from Belarus Math Olyimpiads? Tnx
IceWolf10
01.06.2021 18:26
Should the two answers in part (b) of @2above's solution be switched around?
zaidova
20.11.2024 23:02
a) $n=even$ the answer is $n^2/2$ $n=odd$ the answer is $(n^2+1)/2$
Attachments:
