МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Занятие 9 (ноябрь 1993). Раскраски

Задача 1. Замок барона Мюнхгаузена имеет вид прямоугольника размером 7*9 клеток. Каждая клетка, кроме центральной, - комната замка, а в центральной клетке находится бассейн. В каждой стене (стороне клетки), разделяющей две соседние комнаты, проделана дверь. Можно ли, не выходя из замка и не заходя в бассейн, обойти все комнаты, побывав в каждой ровно по одному разу?

Задача 2. Можно ли покрыть доску 8*8 с вырезанной угловой клеткой фигурками вида

       -                         -
      | |                       | |
     - -       - - -           - -         - - -
a)  | | |  и  | | | |     б)  | | |    в) | | | |
     - -       - - -           - -         - - -

Задача 3. В Парламенте некоторой страны 100 депутатов. По крайней мере один из них честен. В каждой паре депутатов хотя бы один продажен. Сколько всего честных депутатов?

Задача 4. В классе 25 учеников. Докажите, что в этом классе найдутся 2 ученика, которые отмечают свой день рождения в одном и том же месяце. А найдутся ли 3 таких ученика?

Задача 5. На доске размером 8*8 клеток в левом нижнем углу в виде квадрата 3*3 стоят девять фишек (смотрите рисунок слева). За один ход разрешается какой-нибудь одной фишке перепрыгнуть через какую-нибудь другую фишку на клетку, симметричную первой фишке относительно второй (если эта клеткас вободна). Можно ли после нескольких таких ходов собрать все фишки в виде квадрата 3*3
а) в левом верхнем углу доски;
б) в правом верхнем углу доски?

   - - - - - - - -
  | | | | | | | | |
   - - - - - - - -
  | | | | | | | | |
   - - - - - - - -
  | | | | | | | | |
   - - - - - - - -
  | | | | | | | | |
   - - - - - - - -
  | | | | | | | | |
   - - - - - - - -
  |o|o|o| | | | | |
   - - - - - - - -
  |o|o|o| | | | | |
   - - - - - - - -
  |o|o|o| | | | | |
   - - - - - - - -

Задача 6. Пароход вниз по реке идет от А до В трое суток, а от В до А - пять суток. Сколько времени будут плыть плоты от А до В?

Объявление 1. Просьба всем преподавателям обязательно привести в порядок кондуиты к следующему занятию.

Объявление 2. Через одну субботу (т. е. 11 декабря) будет занятие по "топологии" (школьники будут клеить листы Мёбиуса, разрезать их на части и т. д. и т. п.) Для этого желательно, чтобы они принесли 11 декабря бумагу, ножницы и клей (кто сможет).

Указания для преподавателей

В начале можно немного поговорить о геометрических задачах прошлых занятий (задача про лесника, задача про хомяка и суслика), что-то разобрав, где-то подсказав идею решения. Затем нужно обязательно рассказать задачу 5 г) прошлого занятия, поскольку основная тема сегодняшнего занятия - раскраски. Обязательно скажите школьникам, что раскраски бывают не только шахматные, и не только в два цвета.

Задача 1 довольно проста (лишь бы школьники это поняли). Нужно раскрасить замок как шахматную доску и заметить, что черные и белые клетки при обходе чередуются. Но из-за вырезанной центральной клетки на доске одного цвета будет на две клетки больше.

Задача 2 в) - уже что-то новое. В ней появляется раскраска, отличная от шахматной - по диагонали в три цвета. Она довольно естественно обобщает шахматную, и будет очень здорово, если школьники это поймут. Разберите эту задачу на втором часу занятия.

Задача 3 очень простая (это, конечно, не значит, что ее все решат).

Задача 4 также не слишком сложна, но имеет важное стратегическое значение - на следующем занятии школьникам будут предложены несколько задач на принцип Дирихле. Можно провести веселый эксперимент: выписать на доску даты рождений школьников из вашей аудитории. С большой вероятностью у кого-то совпадут даже числа.

Задача 5 б) довольно сложна - здесь нужно красить доску в полоску (в два цвета). Придумать такую раскраску самому не очень просто. Желательно нарисовать на доске рисунок, объяснить, как ходят фишки и что спрашивается в пунктах а) и б). Можно сказать школьникам, что решать эту задачу удобнее, скатав из бумаги девять шариков (фишек), а не рисуя и зачеркивая позиции в тетрадке. В конце занятия намекните детям, что в пункте а) все получится с шахматной раскраской, в пункте б) ответ тоже отрицательный, но раскраску нужно придумать другую. После этого мягко посоветуйте порешать эту задачу дома. А в начале следующего занятия расскажите детям решение.

Задача 6 не слишком сложна, но и не слишком проста. Наверняка, часто будут приводить неправильные ответы (типа четырех суток).

Указания к задачам

Задача 1. Ответ: нельзя.

Задача 2.
а), б) Ответ: можно.
в) Ответ: нельзя (раскрасьте доску по диагонали в 3 цвета и посчитайте число клеток каждого цвета. Получится, что одного цвета больше.

Задача 3. Ответ: 1 депутат.

Задача 4. В обоих пунктах ответ: да (по принципу Дирихле).

Задача 5.
а) Ответ: нет (шахматная раскраска).
б) Ответ: нет (раскраска в полоску в два цвета).
В обоих пунктах фишки при отражениях не меняют цвет.

Задача 6. Ответ: 35 суток.