Question

На каждой клетке доски размером 7×7 сидит жук. по свистку каждый из жуков переползает в одну из соседних по диагонали клеток. при этом в некоторых клетках может оказаться больше одного жука, а некоторые клетки окажутся незанятыми. какое минимальное число клеток точно окажутся незанятыми?

Answer 1

Раскрасим клетки доски в шахматном порядке так, чтобы черных клеток было 25, а белых 24. Заметим, что после переползания жуки, сидящие на белых клетках, оказались на чёрных клетках, а жуки, сидящие на чёрных клетках – на белых. Так как белых клеток на одну меньше, чем чёрных, после переползания по принципу Дирихле хотя бы одна чёрная клетка окажется пустой.