Решение. Предположим, что число является произведением двух чисел, состоящих только из единиц и нулей. Что может быть его последней цифрой? Только 1 или 0. А последней ненулевой цифрой? Только 1 (потому что произведение последних ненулевых цифр сомножителей – это произведение двух единиц). А что может быть первой цифрой? Тоже только 1. Однако по условию число не может содержать двух единиц. Значит, первая единица и является последней ненулевой цифрой. В таком случае в каждом из сомножителей только одна единица в записи. Но так как оба числа больше 1 (иначе другое равно произведению), оба они заканчиваются на 0, и в произведении найдутся два нуля.
Комментарий. Задача решена методом от противного: мы предположили, что доказываемое утверждение неверно, и пришли к противоречию. Одно из противоречащих друг другу утверждений – условие (число не содержит повторяющихся цифр), а другое – его отрицание.
Задача 7.3. Двое играют в «крестики-нолики» на бесконечной доске. Крестики ходят первыми. Выигрывает тот, кто смог поставить пять своих значков подряд по вертикали, горизонтали или диагонали. Докажите, что крестики могут как минимум не проиграть.
Обсуждение. Поясним, что значит «могут не проиграть». Вдруг крестики – первоклассник, а нолики – выпускник, игравший в «крестики-нолики» на всех уроках в течение одиннадцати лет? Однако в подобных задачах рассматривается игра не реальных людей, а идеальных игроков, способных просчитывать игру на какое угодно число ходов вперед. Исход партии между такими игроками предрешен правилами игры и не зависит от их настроения и самочувствия. Либо у идеальных крестиков есть беспроигрышная стратегия (т. е. возможность ходить так, чтобы не проиграть при любых действиях ноликов) – и тогда он ей непременно воспользуется и сможет не проиграть, либо нет, т. е. у ноликов есть возможность выигрывать всегда, независимо от ходов первого (то есть выигрышная стратегия).
Решение. Предположим противное. Пусть у первого игрока – крестиков – нет беспроигрышной стратегии. Это означает, что у второго есть выигрышная стратегия. В таком случае крестики могут сделать первый ход куда угодно, а затем руководствоваться выигрышной стратегией второго игрока. Если эта стратегия говорит ему поставить крестик туда, где он уже стоит, надо просто поставить его куда угодно, от этого хуже не будет. Таким образом, если выигрышная стратегия есть у ноликов, то она есть и у крестиков. Но у них не может быть одновременно выигрышных стратегий. Полученное противоречие показывает, что предположение неверно, и крестики при безошибочной игре не проиграют.
