Kat&Pop - Рефераты - Программа ВМШ - семестр 2, занятие 10.

Занятие десятое. (26.11.2000г.)

Принцип Дирихле

Контрольная работа.

  1. В школе заведено, что каждый ученик в свой день рождения угощает конфетой директора школы. Докажите, что в какой-то день директора угостят трое, если известно, что в школе 800 учеников.
  2. В четверговую школу пришли ученики, причем некоторые были знакомы раньше. Доказать, что найдутся двое, у которых было одинаковое количество знакомых среди учеников школы до прихода в школу.
  3. Зачет сдавало 49 учеников. Каждый ученик решал 1 легкую и 1 сложную задачу. Докажите, что, по крайней мере, 2 ученика решали одинаковый набор задач, если известно, что преподаватели подготовили 8 простых и 6 сложных задач.
  4. Четырнадцать учеников решали задачи. Всего было решено 90 задач. Докажите, что какие-то два ученика решили одинаковое число задач.
  5. Докажите, что разность каких-то двух степеней семерки делится на 2000.
  6. Можно ли расставить на шахматной доске 17 королей так, чтобы они не били друг друга?

Игры. Выигрышные и проигрышные стратегии

  1. По полоске клетчатой бумаги длиной 20 клеток двое играющих по очереди передвигают фишку влево на 2, 4 или 7 клеток. Проигрывает игрок, которому некуда ходить.

Комментарий: Для нахождения выигрышных стратегий определяются выигрышные и проигрышные позиции со следующими свойствами:

  1. конечная позиция выигрышная;
  2. из любой выигрышной позиции всегда существует ход в невыигрышную позицию;
  3. из любой невыигрышной позиции за один ход можно попасть только в выигрышную.

  1. Ладья стоит на поле а1. За один ход ее можно двигать вверх или вправо. Проигрывает тот, кому некуда ходить.
  2. Ферзь стоит на поле с1. За ход его разрешается передвинуть на любое число полей вправо, вверх или по диагонали "вправо-вверх". Выигрывает тот, кто поставит ферзя на поле h8.
  3. Имеется две кучки конфет: в одной - 20, в другой - 21 конфета. За один ход разрешается съесть одну из кучек, а вторую разделить на две меньшие (не обязательно равные) кучки. Проигрывает тот, кто не сможет сделать хода. Кто выигрывает при правильной игре?
  4. На столе лежат 20 спичек. Игрок может взять 2, 3, или 4 спички, но не может взять столько, сколько взял предыдущий. Кто не может сходить – проигрывает.
  5. Вначале на столе две кучки по 11 орехов. В свой ход нужно съесть 2 ореха из одной (любой) кучки и 1 орех из другой. Проигрывает тот, кто не сможет сделать ход. Кто выигрывает, Петя или Вася?
  6. *Сашенька и Пашенька играют на бесконечной полоске клетчатой бумаги в следующую игру. Сашенька ставит два крестика, а Пашенька стирает любое число подряд идущих крестиков. Сможет ли Пашенька помешать Сашеньке выставить 2000 крестиков в ряд?
  7. Два игрока по очереди ходят ладьей, начиная с верхнего поля. При этом запрещается ставить ладью на поле, где она уже побывала. Проигрывает игрок, который не может сделать ход.

Домашняя работа.

  1. В каждой клетке на доске 7´ 7 сидит жук. По команде все жуки переползают на соседние по стороне клетки. Доказать, что после этого какая-то клетка останется пустой.
  2. Докажите, что доску 8´ 8 нельзя замостить 15 фигурками 1´ 4 и одной фигуркой из четырех клеток в форме буквы "Г".
  3. Докажите, что квадрат 6´ 6 нельзя разрезать на 11 прямоугольников 1´ 3 и один уголок из трех клеток.
  4. Найдите закономерность и продолжите ряд 2, 5, 8, 11, … . Найдите 2000-ый член этой последовательности. Найдите ее n-ый член.