ШКОЛА В «КВАНТЕ»
Где ошибка?
(Логика, комбинаторика, вероятность)
ВПРЕДЛАГАЕМЫХ ТЕКСТАХ МОГУТ БЫТЬ ошибки (как в условиях задач, так и в ответах и решениях). Попытайтесь их найти там, где они есть. Задача 1. На острове живут рыцари и лжецы. Как-то за круглым столом собралось 12 островитян. Каждый их них сказал: «Оба моих соседа – лжецы». Сколько лжецов было за столом? Ответ: 6. Решение. Все сидящие за столом не могли быть лжецами, так как тогда для каждого из них высказывание было бы верным. Значит, за столом был хотя бы один рыцарь. Его правый сосед – лжец, так как рыцарь сказал правду. Правый сосед лжеца – рыцарь, так как лжец солгал. Правый сосед этого рыцаря – лжец и так далее. Таким образом, рыцари и лжецы сидят через одного, следовательно, лжецов было 6. Рассуждение выглядит правдоподобным. Ошибок нет? Задача 2. Вася и Петя закрашивают по очереди клетки на доске размером 4 u 4 так, чтобы не образовывался из закрашенных клеток. Тот, кто не сможет сделать очередной ход, проигрывает. Начинает Петя. Кто из них сможет выиграть, как бы ни играл соперник? Ответ: Вася. Решение. Как бы ни играли Вася и Петя, они обязательно сделают в сумме 12 ходов. Тринадцатый ход должен будет сделать Петя, поэтому он проиграет. А почему обязательно 12 ходов? Задача 3. Дана клетчатая доска размером с шахматной раскраской. За один шаг можно выбрать на этой доске произвольный квадрат размером 2 u 2 и изменить цвет каждой его клетки на противоположный. Можно ли за несколько шагов сделать так, чтобы все клетки доски оказались одного цвета? Ответ: нельзя. Решение. Заметим, что при перекрашивании любого квадрата 2 u 2 в любой строке
доски остаются две белые и две черные клетки. Следовательно, все клетки не могут оказаться одного цвета. Кажется, найден требуемый инвариант. Но не слишком ли просто? Задача 4. Рассматриваются «слова» длины 100, составленные только из букв A, B и C. Каких слов больше: тех, в которых каждый из фрагментов AB и AC встречается четное число раз, или тех, в которых каждый из таких фрагментов встречается нечетное число раз? Ответ: поровну. Решение. Рассмотрим слово, в котором оба фрагмента встречаются нечетное число раз. Заменим в нем первый из фрагментов на другой (AB на AC или наоборот). Получим слово, у которого оба фрагмента встречаются четное число раз. Это соответствие является взаимно однозначным, поэтому слов обоих видов одинаковое количество. Типичное рассуждение для подобных задач. Интересно, а можно ли было начать рассуждение со слов, в которых оба фрагмента встретятся четное число раз? Задача 5. Два приятеля пришли на базар. Веселый молодец продавал 20 котов по цене от 12 до 15 рублей и 20 мешков по цене от 30 копеек до 1 рубля. Докажите, что каждый из друзей может купить по коту в мешке так, чтобы они заплатили одинаковую сумму денег. Решение. Заметим, что наименьшая стоимость кота в мешке – 12 рублей 30 копеек, а наибольшая – 16 рублей. Следовательно, количество вариантов возможных стоимостей кота в мешке не превышает количества целых чисел на отрезке [1230; 1600], т.е. не больше 371. Вместе с тем, количество различных пар вида «кот–мешок» равно 20 20 400. Следовательно, по принципу Дирихле найдутся две пары, имеющие одинаковую стоимость. С принципом Дирихле спорить трудно. А если все-таки попробовать? Задача 6. В турнире по круговой системе участвовали 8 шахматистов (каждый участник встретился с каждым один раз). За победу начислялось 1 очко, за ничью – 0,5 очка, за поражение – 0. В результате все участники набрали различное количество очков. Затем часть шахматистов была дисквалифицирована и результаты поедин-