Грустная новость: британский специалист по науке о данных Ник Берри, автор блога DataGenetics, предназначенного для популяризации математики (одного из самых старых и популярных), покинул нас в начале октября 2022 в возрасте 55 лет, не сумев побороть рак.
Ник родился в Йоркшире, изучал авиационную технику в Саутгемптонском университете, потом переехал в Сиэтл, где работал специалистом по науке о данных на различные компании, включая Microsoft и Facebook. Блог DataGenetics он начал вести в 2009. Достаточно быстро проект набрал большое количество подписчиков: всё благодаря простому языку и интересным темам из области математики, физики и информатики.
Ник всегда мог найти интересную тему для обсуждения и доступно объяснить её, а также получал истинное удовольствие от этого процесса. Любил он и хорошие задачки-загадки. Сегодняшние задачки взяты из его блога.
1. Без нулей
Напишите, как можно получить 1 000 000, перемножив два числа, не содержащие нулей. Подсказка: 10 x 10 x 10 x 10 x 10 x 10 = 1 000 000.
Решение
15625 x 64
Поскольку 10 = 2 x 5, получается, что миллион — это 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5. Ответ можно получить, определённым образом сгруппировав двойки и пятёрки. Группировать их нужно так, чтобы ни в одном из двух чисел не было нулей – а значит, ни одно из них не должно содержать среди множителей одновременно двойки и пятёрки.
Поскольку 10 = 2 x 5, получается, что миллион — это 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5. Ответ можно получить, определённым образом сгруппировав двойки и пятёрки. Группировать их нужно так, чтобы ни в одном из двух чисел не было нулей – а значит, ни одно из них не должно содержать среди множителей одновременно двойки и пятёрки.
2. Тайное число Люси
На вечеринке вы случайно подслушали разговор между Люси и её подружкой. Люси упомянула, что у неё есть тайное число, не превышающее 100. При этом его можно однозначно описать, ответив на четыре следующих вопроса:
1) Делится ли число на два?
2) Делится ли число на три?
3) Делится ли число на пять?
4) Делится ли число на семь?
Ответ она уже прошептала подруге на ушко. К сожалению, из-за шума на вечеринке вы уловили только ответ на один вопрос – «да». Однако один только этот ответ позволит вам определить её тайное число.
Решение
70
Поскольку у нас есть четыре вопроса, на каждый из которых ответ может быть «да» или «нет», мы имеем 16 вариантов ответов. Люси сказала, что её число можно однозначно описать, ответив на эти вопросы. Давайте посмотрим на те из возможных комбинаций, которые определяют одно-единственное число.
Начнём с комбинации нет, нет, нет, нет. Мы получим числа 11, 13, и несколько других – поэтому данная комбинация нам не подходит.
Теперь попробуем нет, нет, нет, да. Получаем 7, 49 и ещё парочку – вычёркиваем и её.
Пройдя все комбинации таким способом, мы получим только две, из которых следует единственное число.
Нет, нет, да, да даёт 35.
Да, нет, да, да даёт 70.
У нас получается два варианта, 35 и 70.
При этом ответы на второй, третий и четвёртый вопрос – делится ли число на 3, 5 и 7 – для обоих чисел одинаковые. Но по условию задачи, мы можем определить число, зная ответ только на один вопрос – получается, это должен быть первый вопрос, делится ли число на 2. И раз мы знаем, что ответ на этот вопрос – «да», получается, что секретное число Люси равно 70.
Поскольку у нас есть четыре вопроса, на каждый из которых ответ может быть «да» или «нет», мы имеем 16 вариантов ответов. Люси сказала, что её число можно однозначно описать, ответив на эти вопросы. Давайте посмотрим на те из возможных комбинаций, которые определяют одно-единственное число.
Начнём с комбинации нет, нет, нет, нет. Мы получим числа 11, 13, и несколько других – поэтому данная комбинация нам не подходит.
Теперь попробуем нет, нет, нет, да. Получаем 7, 49 и ещё парочку – вычёркиваем и её.
Пройдя все комбинации таким способом, мы получим только две, из которых следует единственное число.
Нет, нет, да, да даёт 35.
Да, нет, да, да даёт 70.
У нас получается два варианта, 35 и 70.
При этом ответы на второй, третий и четвёртый вопрос – делится ли число на 3, 5 и 7 – для обоих чисел одинаковые. Но по условию задачи, мы можем определить число, зная ответ только на один вопрос – получается, это должен быть первый вопрос, делится ли число на 2. И раз мы знаем, что ответ на этот вопрос – «да», получается, что секретное число Люси равно 70.
3. Эльфы-хулиганы
Я записал целые числа от 1 до 9999 включительно на огромной школьной доске. Каждое из чисел написано там только по разу.
Ночью к доске получила доступ банда эльфов-хулиганов. Каждый из них подходил к доске, стирал два случайных числа и писал вместо них одно число – разницей между этими числами (по модулю разницы, т.е. абсолютное значение). Описанный вандализм продолжался всю ночь, пока на доске в результате вакханалии не осталось только одно число.
Вернувшись к доске следующим утром, я обнаружил на ней единственное число. Было ли оно чётным или нечётным?
Решение
Число будет чётным.
Очевидно, оставшееся на доске число может быть только чётным или нечётным. В начале ночи на доске написано 9999 чисел. 5000 из них нечётные, 4999 – чётные.
Когда эльф выбирает пару чисел, на доске могут произойти изменения всего трёх видов. Он может выбрать два нечётных числа, два чётных или по одному числу каждого типа.
Если он выберет два нечётных числа, разница между ними всегда будет чётной. Тогда количество нечётных чисел на доске уменьшится на 2.
Если он выберет два чётных числа, разница между ними тоже будет чётной. Тогда количество нечётных чисел на доске не изменится.
Если он выберет чётное и нечётное число, разница между ними будет нечётной. Мы потеряем одно нечётное число, зато получим ещё одно. По итогу количество нечётных чисел останется тем же.
Получается, что количество нечётных чисел на доске после каждого акта вандализма либо не меняется, либо уменьшается на два.
Изначально на доске было 5000 нечётных чисел, что является чётным количеством. Если мы будем всегда уменьшать его на 2, то оно будет оставаться чётным, и в итоге дойдёт до нуля.
Следовательно, если на доске осталось одно число, оно должно быть чётным.
Очевидно, оставшееся на доске число может быть только чётным или нечётным. В начале ночи на доске написано 9999 чисел. 5000 из них нечётные, 4999 – чётные.
Когда эльф выбирает пару чисел, на доске могут произойти изменения всего трёх видов. Он может выбрать два нечётных числа, два чётных или по одному числу каждого типа.
Если он выберет два нечётных числа, разница между ними всегда будет чётной. Тогда количество нечётных чисел на доске уменьшится на 2.
Если он выберет два чётных числа, разница между ними тоже будет чётной. Тогда количество нечётных чисел на доске не изменится.
Если он выберет чётное и нечётное число, разница между ними будет нечётной. Мы потеряем одно нечётное число, зато получим ещё одно. По итогу количество нечётных чисел останется тем же.
Получается, что количество нечётных чисел на доске после каждого акта вандализма либо не меняется, либо уменьшается на два.
Изначально на доске было 5000 нечётных чисел, что является чётным количеством. Если мы будем всегда уменьшать его на 2, то оно будет оставаться чётным, и в итоге дойдёт до нуля.
Следовательно, если на доске осталось одно число, оно должно быть чётным.
