Четность

Подборка олимпиадных задач по теме "Четность".

1. На столе лежат 13 шестеренок, соединенных в замкнутую цепочку. Могут ли все шестеренки вращаться одновременно? Может ли прямая, не содержащая вершин замкнутой 13-звенной ломаной, пересекать все ее звенья?
2. Можно ли нарисовать 13-звенную замкнутую ломаную, каждое звено которой пересекается ровно с одним из остальных звеньев?
3. На доске $25\times25$ расставлены 25 шашек, причем их расположение симметрично относительно диагонали. Докажите, что одна из шашек расположена на диагонали.
4. На доске $25\times25$ расставлены 25 шашек, причем их расположение симметрично относительно обеих главных диагоналей. Докажите, что одна из шашек стоит в центральной клетке.
5. Квадратная таблица $25\times25$ раскрашена в 25 цветов так, что в каждой строке и в каждом столбце представлены все цвета. Докажите, что если расположение цветов симметрично относительно одной из диагоналей, то на этой диагонали тоже представлены все цвета.
6. Конь вышел с поля $a1$ шахматной доски и через несколько ходов вернулся на него. Докажите, что он сделал четное число ходов.
7. Может ли конь пройти с поля $a1$ на поле $h8$, побывав по дороге на каждом из остальных полей ровно один раз?
8. Можно ли все клетки таблицы $1000 \times 1001$ заполнить натуральными числами так, чтобы сумма чисел в любом столбце и в любой строке были бы простыми числами?
9. Простые числа имеют только два различных делителя -- единицу и само это число. А какие натуральные числа имеют только три различных делителя?
10. Все костяшки домино выложили в ряд по правилам игры. На одном конце оказалось шесть очков. Сколько очков на другом конце?
11. Из набора домино выбросили все кости с пустышками. Можно ли все оставшиеся кости выложить в ряд?
12. Кузнечик прыгает по прямой. В первый раз он прыгнул на 1 см в какую-то сторону, во второй раз -- на 2 см, в третий -- 3 см и так далее. Докажите, что после 1001 прыжка он не может оказаться там, где начинал.
13. В классе 30 учеников и каждый день трое из них дежурят по классу. Может ли через некоторое время оказаться так, что каждый с каждым дежурил ровно один раз?
14. За круглым столом сидят 25 мальчиков и 25 девочек. Докажите, что у кого-то из сидящих за столом оба соседа -- мальчики.
15. На доске записано число 123456789. У написанного числа выбираются две соседние ненулевые цифры, из каждой из них вычитается по единице, и выбранные цифры меняются местами. Какое наименьшее число может быть получено в результате таких операций?
16. Сережа написал на доске в некотором порядке 2012 плюсов и 2013 минусов. Время от времени Леша подходит к доске, стирает любые два знака и пишет вместо них один, причем если он стер одинаковые знаки, то вместо них он пишет плюс, а если разные, то минус. После нескольких таких действий на доске остался только один знак. Какой это мог быть знак?
17. В клетки таблицы $4\times 4$ записаны числа $1$ и $-1$ так, что в каждой строке, в каждом столбце и на каждой диагонали (не обязательно главной; в частности, в угловых клетках) произведения чисел равны 1. Какое максимальное число минус единиц может быть в таблице?
18. Дан набор из 239 чисел таких, что если каждое число в наборе заменить на сумму остальных чисел, то получится тот же набор. Найдите произведение всех чисел набора.
19. Есть 101 монета, из которых 50 фальшивых, отличающихся по весу на 1 грамм от настоящих (либо легче, либо тяжелее). Петя выбрал одну монету и за одно взвешивание на весах со стрелкой, показывающей разность весов на чашках, хочет определить фальшивая ли она. Сможет ли он это сделать?
20. Можно ли выписать в ряд по одному разу цифры от 1 до 9 так, чтобы между единицей и двойкой, двойкой и тройкой, ..., восьмеркой и девяткой было нечетное число цифр?
21. Можно ли выписать в ряд цифры от 1 до 9 по два раза каждую так, чтобы между единицами была одна цифра, между двойками -- две, ..., между девятками было девять цифр?
22. На шахматной доске $8 \times 8$ на каждой клетке стоит шашка, с одной стороны белая, с другой черная. За один ход можно выбрать любую шашку и перевернуть ее и все шашки, стоящие с ней на одной вертикали и на одной горизонтали. Правда ли, что при любой начальной расстановке шашек можно сделать так, чтобы все шашки лежали белой стороной вверх?
23. Дано $n$ чисел $x_1$, $x_2$, ..., $x_n$, каждое из которых равно $+1$ или $-1$. Известно, что $$ x_1x_2 + x_2x_3 + \ldots + x_{n-1}x_n + x_nx_1 = 0. $$ Докажите, что $n$ делится на 4.
24. На плоскости нарисован многоугольник. Прямая $l$ пересекает ее в 999 точке. Докажите, что существует прямая, пересекающая этот многоугольник по крайней мере в 1000 точках.
25. B cтаде 101 корова. Если увести любую из них, то оставшихся можно разделить на два стада по 50 коров в каждом, так что суммарный вес коров одного стада равен суммарному весу коров другого стада. Известно, что каждая корова весит целое число килограммов. Докажите, что все коровы весят одинаково.
26. По кругу расставлены 1001 натуральное число. Докажите, что найдутся два соседних числа такие, что после их выкидывания оставшиеся числа нельзя разбить на две группы с равной суммой.
27. Можно ли окрасить на клетчатой бумаге 25 клеток так, чтобы у каждой из них было нечетное число соседних по стороне окрашенных клеток?
28. За круглым столом совещались $2n$ депутатов. После перерыва эти же $2n$ депутатов расселись вокруг стола, но уже в другом порядке. Доказать, что найдутся два депутата, между которыми как до, так и после перерыва сидело одинаковое число человек.
29. В небольшом городке стояла школа, в которой учились ровно 1000 школьников. У каждого из них был шкаф для одежды -- всего 1000 шкафов, причём шкафы были пронумерованы числами от 1 до 1000. А ещё в этой школе жили привидения -- ровно 1000 привидений. Каждый школьник, уходя из школы, запирал свой шкаф, а ночью привидения начинали играть со шкафами, то отпирая, то запирая их. Однажды вечером школьники, как обычно, оставили запертыми все шкафы. Ровно в полночь появились привидения. Сначала первое привидение открыло все шкафы, потом второе привидение закрыло те шкафы, номер которых делился на 2, затем третье привидение поменяло позиции (т.е. открыло шкаф, если он был закрыт, и закрыло -- если он был открыт) тех шкафов, номер которых делился на 3; следом за ним четвёртое привидение поменяло позиции тех шкафов, номер которых делился на 4 и т.д. Как только тысячное привидение поменяло позицию тысячного шкафа -- включилась сигнализация, и все привидения срочно убрались восвояси. Сколько осталось открытых шкафов после посещения привидений?
30. Переаттестация Совета из 100 мудрецов происходит так: король выстраивает их в колонну по одному и надевает на голову каждому колпак белого или черного цвета. Каждый мудрец видит цвета колпаков всех впереди стоящих мудрецов, но не видит цвет своего колпака и цвета колпаков мудрецов, стоящих сзади него. Затем мудрецы по одному называют какой-нибудь цвет (каждому разрешается говорить ровно один раз; то, что говорит один мудрец, слышат все). После этого король казнит всех мудрецов, назвавших цвет, отличный от цвета своего колпака. Накануне переаттестации все члены Совета договорились между собой и придумали, как минимизировать число казненных. Скольким из них гарантированно удастся избежать казни?
31. Окружность разбита точками на $3k$ дуг: по $k$ дуг длиной 1, 2 и 3. Докажите, что найдутся две диаметрально противоположные точки деления.