Олимпиадные задачи из источника «31 турнир (2009/2010 год)» - сложность 4 с решениями

У входа в пещеру стоит барабан, на нём по кругу через равные промежутки расположены<i>N</i>одинаковых с виду бочонков. Внутри каждого бочонка лежит селёдка – либо головой вверх, либо головой вниз, но где как – не видно (бочонки закрыты). За один ход Али-Баба выбирает любой набор бочонков (от 1 до<i>N</i>штук) и переворачивает их все. После этого барабан приходит во вращение, а когда останавливается, Али-Баба не может определить, какие бочонки перевёрнуты. Пещера откроется, если во время вращения барабана все<i>N</i>селёдок будут расположены головами в одну сторону. При каких<i>N</i>Али-Баба сможет открыть пещеру?

Оля и Максим оплатили путешествие по архипелагу из 2009 островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что Оля может выиграть.

На клетчатую плоскость положили 2009 одинаковых квадратов, стороны которых идут по сторонам клеток. Затем отметили все клетки, которые покрыты нечётным числом квадратов. Докажите, что отмеченных клеток не меньше, чем клеток в одном квадрате.