Математические игры с дурацкими рисунками: 75¼ простых, но требующих сообразительности игр, в которые можно играть где угодно

Мне кажется удивительным то, что в эту оптимальную систему входят три монеты, находящиеся в реальном обращении. Под «удивительным» я имею в виду «банальное». Лично мне нравятся номиналы 1¢, 3¢, 13¢ и 31¢. Всего нужно 400 монет с такими номиналами, чтобы составить все суммы, но зато мы привносим анархию в виде монет с номиналами 13¢ и 31¢.

Примечание: мы обычно составляем суммы, начиная с монет с наибольшим номиналом. Например, чтобы составить сумму 72¢, мы используем максимальное число квотеров (2), затем максимальное число даймов (2), затем максимальное число никелей (0) и, наконец, одноцентовые монеты (2). Такой подход называют «жадным алгоритмом», и наша система номиналов цент-никель-дайм-квотер минимизирует число необходимых монет.

Но это правило не действует в системе 1–5–18–25¢. Например, жадный алгоритм требует для составления 72¢ семь монет (два квотера, одну монету 18¢ и четыре одноцентовика), когда есть возможность обойтись всего четырьмя монетами (по 18¢). Поэтому эффективно составить какую-нибудь сумму в этом мире значительно сложнее!

Если вы настаиваете на использовании только жадного алгоритма, то наилучшей будет система 1¢, 3¢, 11¢ и 37¢ (при это требуется 410 монет).

Может ли какая-либо вариация правил привести к бесконечной игре? Нет. Давайте для начала рассмотрим «идеальный размен». Каждый цент дает один ход, каждый пятицентовик – до шести ходов (один ход для размена его на центы, а затем пять одноцентовых ходов). Каждый десятицентовик дает до 13 ходов (один для его размена на пятицентовики, затем шесть на каждый пятицентовик). Ну а каждый четвертак дает до 33 ходов (один для его размена на два десятицентовика и пятицентовик, затем 13 на каждый десятицентовик и шесть на пятицентовик). Таким образом, исходная сумма дает максимум 33 + (13 + 13) + (6 + 6 + 6 + 6) + (1 + 1 + 1 + 1 + 1) = 88 ходов.

Ну а если будет «более чем идеальный размен»? Скажем, у нас пять игроков. Цент по-прежнему дает один ход. Пятицентовик в лучшем случае может быть обменян на все 20 центов, которые есть в игре, а это даст максимум 21 ход. Десятицентовик в лучшем случае может быть обменян на все 15 пятицентовиков (каждый из которых дает 21 ход) и все 20 центов (каждый из которых дает один ход), в сумме это 336 ходов. Ну а четвертак в лучшем случае может быть обменян на все 10 десятицентовиков (каждый из которых дает 336 ходов), плюс все пятицентовики и центы (которые эквивалентны 11-му десятицентовику), в сумме это 3696 ходов. Таким образом, в игре не может быть больше, чем 4435 ходов.

ПРОРОЧЕСТВА

Полегче там! От этих автореферентных штучек можно свихнуться. Это только начало; есть много чего способного свести с ума. Попробуйте посмотреть книги Дугласа Хофштадтера Gödel Escher Bach: An Eternal Golden Braid (New York: Basic Books, 1979) (Хофштадтер Д. Гёдель, Эшер, Бах: Эта бесконечная гирлянда. – М.: Бахрах-М, 2001) и Metamagical Themas: Questing for the Essence of Mind and Pattern (New York: Basic Books, 1985). О Бертране Расселле, Курте Гёделе и истории логики в XX веке я советую почитать Apostolos Doxiadis and Christos Papadimitriou, Logicomix: An Epic Search for Truth (New York: Bloomsbury USA, 1999).

Я не хочу что-то там читать. Меня интересуют задачи! Увлекательные (и непростые) головоломки, ведущие от элементарной логики к теоремам Гёделя, я рекомендую поискать в Raymond Smullyan, To Mock a Mockingbird (New York: Oxford University Press, 1982) (Смаллиан Р. Передразнить пересмешника и другие логические загадки, включая увлекательное путешествие в комбинаторную логику. – М.: Лори, 2022).

Как вы придумали такую автореферентную таблицу? Это классическая головоломка, хотя я не видел, чтобы ее представляли в табличной форме раньше. См.: Alex Bogomolny, "Place Value," Cut the Knot! July 1999 (https://www.cut-the-knot.org/ctk/SelfDescriptive.shtml).

Существуют ли другие автореферентные таблицы? Конечно, вот они, включая ту, что приведена в главе.

Если вы хотите, чтобы в таблице были числа от 1 до n, то знайте, что это исчерпывающий список[107].

ДРУГИЕ ЧИСЛОВЫЕ ИГРЫ