Грустная новость: британский специалист по науке о данных Ник Берри, автор блога 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.
Поскольку 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) Делится ли число на семь?
Ответ она уже прошептала подруге на ушко. К сожалению, из-за шума на вечеринке вы уловили только ответ на один вопрос – «да». Однако один только этот ответ позволит вам определить её тайное число.
Поскольку у нас есть четыре вопроса, на каждый из которых ответ может быть «да» или «нет», мы имеем 16 вариантов ответов. Люси сказала, что её число можно однозначно описать, ответив на эти вопросы. Давайте посмотрим на те из возможных комбинаций, которые определяют одно-единственное число.
Начнём с комбинации нет, нет, нет, нет. Мы получим числа 11, 13, и несколько других – поэтому данная комбинация нам не подходит.
Теперь попробуем нет, нет, нет, да. Получаем 7, 49 и ещё парочку – вычёркиваем и её.
Пройдя все комбинации таким способом, мы получим только две, из которых следует единственное число.
Нет, нет, да, да даёт 35.
Да, нет, да, да даёт 70.
У нас получается два варианта, 35 и 70.
При этом ответы на второй, третий и четвёртый вопрос – делится ли число на 3, 5 и 7 – для обоих чисел одинаковые. Но по условию задачи, мы можем определить число, зная ответ только на один вопрос – получается, это должен быть первый вопрос, делится ли число на 2. И раз мы знаем, что ответ на этот вопрос – «да», получается, что секретное число Люси равно 70.
3. Эльфы-хулиганы
Я записал целые числа от 1 до 9999 включительно на огромной школьной доске. Каждое из чисел написано там только по разу.
Ночью к доске получила доступ банда эльфов-хулиганов. Каждый из них подходил к доске, стирал два случайных числа и писал вместо них одно число – разницей между этими числами (по модулю разницы, т.е. абсолютное значение). Описанный вандализм продолжался всю ночь, пока на доске в результате вакханалии не осталось только одно число.
Вернувшись к доске следующим утром, я обнаружил на ней единственное число. Было ли оно чётным или нечётным?
Очевидно, оставшееся на доске число может быть только чётным или нечётным. В начале ночи на доске написано 9999 чисел. 5000 из них нечётные, 4999 – чётные.
Когда эльф выбирает пару чисел, на доске могут произойти изменения всего трёх видов. Он может выбрать два нечётных числа, два чётных или по одному числу каждого типа.
Если он выберет два нечётных числа, разница между ними всегда будет чётной. Тогда количество нечётных чисел на доске уменьшится на 2.
Если он выберет два чётных числа, разница между ними тоже будет чётной. Тогда количество нечётных чисел на доске не изменится.
Если он выберет чётное и нечётное число, разница между ними будет нечётной. Мы потеряем одно нечётное число, зато получим ещё одно. По итогу количество нечётных чисел останется тем же.
Получается, что количество нечётных чисел на доске после каждого акта вандализма либо не меняется, либо уменьшается на два.
Изначально на доске было 5000 нечётных чисел, что является чётным количеством. Если мы будем всегда уменьшать его на 2, то оно будет оставаться чётным, и в итоге дойдёт до нуля.
Следовательно, если на доске осталось одно число, оно должно быть чётным.
Комментарии (32)
sena
19.10.2022 00:36+6Либо вторая задача некорректно сформулирована, либо ответ некорректно сформулирован - в условии не сказано, что удалось расслышать вопрос, напротив, сказано что "один только этот ответ позволит...". А если не удалось расслышать, на какой именно вопрос был дан ответ "да", то мы не можем считать что ответ был на первый вопрос. Если же сформулировать, как "вы услышали только лишь один вопрос и ответ на него был 'да'", тогда нормально.
Akina
19.10.2022 01:20+1Набору "нет, нет, да, да" в первой сотне соответствует только одно число 35.
Набору "да, нет, да, да" соответствует только одно число 70.
Чтобы правильный ответ был единственный, вроде бы нужно именно "К сожалению, из-за шума на вечеринке вы уловили только ответ на первый вопрос – «да»." И тогда этот ответ - 70. Но это не так. Последняя фраза "Однако один только этот ответ позволит вам определить её тайное число." - это не просто сообщение, а часть условия. То есть это утверждение, что Вы можете определить число. А это возможно лишь в случае, если услышан ответ на именно первый вопрос.
sena
19.10.2022 01:53В формулировке содержится ложное утверждение. Там говорится, что "один только этот ответ позволит определить её тайное число", но это ложное утверждение. Одного этого ответа недостаточно, потому что в описанных обстоятельствах - вы сидели с двумя девушками, услышали условия изложенные девушкой и потом её единственный ответ на неизвестный(!) вопрос, дать ответ невозможно, потому что надо ещё знать, на какой вопрос он был дан!
Нет, речь идёт именно о некорректной формулировке, а не о недостаточности данных.
Достаточно изменить формулировку и сказать "К сожалению, из-за шума на вечеринке вы уловили только один какой-то вопрос и ответ на него – «да»" и задача станет корректной, без того чтобы сообщать дополнительную информацию. Если это переводная статья, хотел бы я взглянуть на оригинал, там наверное формулировка корректна.
Другой корректный вариант - "девушка заметила что я услышал единственный ответ 'да' и добавила, что того ответа, что я услышал, мне будет достаточно". Тогда условие добавляется в описанные обстоятельства и воспринимается как условие задачи.
Akina
19.10.2022 12:21В формулировке содержится ложное утверждение. Там говорится, что "один только этот ответ позволит определить её тайное число", но это ложное утверждение.
Это не так. Эта формулировка существует не самостоятельно, а в комплексе с остальными.
Собственно, в задаче есть два связанных между собой факта:
Факт первый - есть утверждение, что загаданное число "можно однозначно описать, ответив на четыре следующих вопроса". Мы уже пришли к выводу, что такой формулировке при известных ответах на все 4 вопроса соответствуют числа 35 и 70.
Факт второй - есть утверждение, что "один только этот ответ позволит вам определить её тайное число".
Теперь давайте определим вот что: ответ на какой из 4 вопросов делает второе утверждение, второй факт, истинным?
Очевидно, что "да" в принципе не может быть ответом на вопрос 2 - в обоих вариантах там должно быть "нет".
Также это не может быть ответом на вопрос 3 или 4 - оба варианта содержат там "да", и мы по-прежнему не можем однозначно определить число и сделать второй факт истинным.
Остаётся единственный вариант - это ответ на вопрос 1. И соответственно загаданное число - 70.
ss-nopol
20.10.2022 16:17Факт второй - есть утверждение, что "один только этот ответ позволит вам определить её тайное число".
Какому "мне" известен этот второй факт? Тому что сидит с девушками или тому что читает Хабр? Тому "мне", что сидит с девушками этот факт неизвестен, потому что девушка его не сказала!
Megakazbek
19.10.2022 02:37+4Всё, что известно подслушивающему - это ответ "да" на какой-то вопрос, а это могло случится и в случае 70 и в случае 35. Тут единственного правильного ответа в принципе быть не может (и не поможет даже фраза в условии), т.к. ответ "да" не разделяет эти ситуации, для этого нужно дополнительно знать, что услышан ответ именно на вопрос, которым ситуации отличаются.
sena
19.10.2022 03:48+1Да, точно, то есть только вторая формулировка в моём ответе, первой будет недостаточно. Девушка должна дать подсказку, что услышанного достаточно.
alexdoublesmile
19.10.2022 04:04Прикольные задачки) Только они скорее арифметические, математика по большей части не имеет ничего общего с числами
Aleksandr-JS-Developer
19.10.2022 12:021. Без нулей
Ага, это легко, а вот для найдёте ли вы решение при
N = 1000002?
Ocelot
19.10.2022 12:19Это ещё легче333334*3
Aleksandr-JS-Developer
19.10.2022 12:23А при
N = 1000019 ?Кстати, интересно, что для каждой степени 10 есть только одно решение и оно равно:
N1 = (5)^p, N2 = (2)^p, где p - это степень, в которую нужно возвести 10, чтобы получить N.Ocelot
19.10.2022 12:26Spoiler header47*21277
Aleksandr-JS-Developer
19.10.2022 12:41Вы уже написали программу или ещё считаете так?)
Ocelot
19.10.2022 12:44Что там писать? factor (N);
Aleksandr-JS-Developer
19.10.2022 12:55Ну, например, для подсчёта случаев
N = 10^500)Ответ N = 10^500
Просто оставлю это тут)
30549363634996046820519793932136176997894027405723266638936139092812916265247204577018572351080152282568751526935904671553178534278042839697351331142009178896307244205337728522220355888195318837008165086679301794879136633899370525163649789227021200352450820912190874482021196014946372110934030798550767828365183620409339937395998276770114898681640625 * 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376
domix32
19.10.2022 14:39ну так для степеней десятки сложность никак не растет. как было 2^n x 5^n = 10^n так и осталось. Или вы хотите числа длиной 100+ символов ручками перепроверять? Помню хотел вручную посчитать сколько же риса там на шахматную доску попадет. После два в сорок какой-то у меня кончилась тетрадь на расчет слагаемых и я забросил это дело.
Aleksandr-JS-Developer
21.10.2022 13:162 ^ 64 - 1 = 18446744073709551615 зёрнышек.
Считали бы долго)))
domix32
21.10.2022 13:34Да я уже будучи студентом вспомнил эту задачку и в экселе за пару кликов вывел.
Aleksandr-JS-Developer
21.10.2022 14:56ну так для степеней десятки сложность никак не растет. как было 2^n x 5^n = 10^n так и осталось
Приводил пример зачем может потребоваться программа :)
А оказалось, что для
N = 10^500решения, походу, нет)
Akina
19.10.2022 19:17Не пойдёть - задание требует, чтобы ни в одном из чисел не было ни одного нуля. Не в конце, а вообще.
Aleksandr-JS-Developer
21.10.2022 12:03Мой косяк. Задания я понимал, но просто слепо доверял этой самой программе, а при копировании нули не заметил
Короче, формула работала для случаев, когда N <= 10 ^ 9.
Т. к.2 ^ 10 = 1024...Прикинул, что формула справедлива для случаев, когда
N = 10 ^ p, p ∈ {1 2 3 4 5 6 7 9 18 33}Хотя для
N > 10*10000не проверял... уж лень 10 мин ждать пока этот медленный JS умножит несколько чисел.Получается, что для некоторых N нет решения. Полный перебор множителей для
N = 10 ^ 10ожидаемо не дал результата без нулей.Конечно, это если мы говорим про целые числа, хотя в задаче не было этого ограничения...
DoNotPanic
19.10.2022 17:26+1как можно получить 1 000 000, перемножив два числа, не содержащие нулей
3E8_16 * 3E8_16 выглядит легальным решением… Числа в другой системе счисления — тоже числа, и нулей в данном случае нет )К сожалению, из-за шума на вечеринке вы уловили только ответ на один вопрос – «да».
Там есть нюанс, который плохо понятен из оригинала, а в русском языке ещё сложнее стало понять… Фишка в том, что тот, кто услышал ответ на вопрос, знает номер вопроса. Номер вопроса просто не сказали читателю, но он однозначен, это не просто информация о том, что у нас среди ответов есть минимум одно «да» (при прочтении впечатление именно такое, но эта информация мусорная, очевидно что загадано не простое число).
Поддерживаю sena, хорошо бы переформулировать.
18741878
20.10.2022 12:17Простое наблюдение к задаче "Без нулей":
10=2*5
100=4*25
1000=8*125
...
1000000=64*15625
Видите закономерность? Проверка:
10000000=128*78125
petropavel
Последнюю можно проще сделать. Запустить вместо эльфов — гномов, которые пишут не разность двух чисел, а их сумму — чётность же от этого не меняется.
А результат — очевидно, сумма всех чисел на доске, и она чётная.
DeathKeeper
Если аппелировать к "четность не меняется", то лучше уж перед эльфами запустить кракена - пусть вместо каждого числа запишет его же по модулю 2.
С 5000 нулями и 4999 единицами несколько проще все смотрится :)