Незнайка подкидывает проблемы…

Всем привет!

Продолжаю путешествие по разным заковыристым математическим и логическим задачкам. Но – увы, плохая новость. Простые задачки у меня совсем закончились, сейчас начнутся немного более сложные. Например, вот такие:

Задачка1. Знайка взял большое число, посчитал его факториал и записал результат на доске. Незнайка пришел и стёр одну цифру. Как её восстановить?

Задачка2. Незнайка стёр две соседние цифры. Как теперь восстановить результат?

Задачка3. Однажды ЖЖ-блогер-путешественник попал в китайский аэропорт. Пароль от вайфая ему сказали, но по-китайски — и блогер не смог его разобрать. Но он понял следующее: пароль от вайфая это такое число, которое при умножении на 4 «переворачивается наоборот», то есть цифры после умножения на 4 меняют порядок на противоположный, что-то вроде «abc..xyz * 4 = zyx..cba». До вылета самолёта остался один час. Вот интересно, успеет ли блогер угадать пароль, подключиться к халявному интернету и отметиться новым блогпостом?

Вот такой пароль точно не подходит…

А пока вы уже задумались, самое время «раскрыть, подсластить и мотивировать» этот процесс, т.е. дать решение предыдущей порции головоломок.

Напоминаю условия.

Задачка 1. Найти все последовательные натуральные чётные (например, 2,4,6,8) числа, сумма которых равна 100.

Очевидно, само число 100 – первая последовательность :)
Далее, если таких числа два, то они должны быть по разным сторонам от 50. Это 49 и 51, но они нечётные. Может ли таких числа быть три? Нет. Поскольку если среднее число X, то остальные X-2 и X+2, их сумма равна 3X. Но 100 на 3 нацело не делится. По этой причине количество чисел в последовательности является делителем 100. Поехали по делителям..

4: 22,24,26,28
5: 16,18,20,22,24
10: Увы, 2+4+6+8+10+12+14+16+18+20=110.

Ответ: {100}, {22,24,26,28}, {16,18,20,22,24}

Задачка 2. По экватору Земли протянута верёвка, которая плотно прилегает к экватору. Её разрезали и вставили +1 метр верёвки. На какое расстояние верёвка поднимется над поверхностью земли?

Пусть радиус Земли R. Длина верёвки будет 2πR. Длина верёвки с метром 2πR+1. Новый радиус равен (2πR+1)/2π = R + 1/2π = R + 0.16 (примерно). То есть, верёвка поднимется на 16 сантиметров. Причём радиус совершенно неважен! Вокруг Земли, Луны, Сатурна или яблока намотана верёвка.

Задачка 3. Какое наименьшее число гирь (вес кратен граммам) требуется для того, чтобы можно было взвесить любое число граммов от 1 до 100 на чашечных весах, если гири можно класть на обе чашки весов?

Гири 1,3 покрывают веса {1,2,3,4}. То есть, добавляя 5+4=9 — добавляя девятку мы покрываем диапазон от 5 до 13. От 14 и выше требуется 14+13=27. Получены все числа от 1 до 1+3+9+27=40. Тем же образом получаем 81. Ура. Нужно всего 5 гирь: 1,3,9,27,81 – степени тройки.

Само собой, что есть избыточность и в качестве третьего груза может быть любой от 60 до 81. (само собой, что могут быть решения типа 1,3,9,22,70). Максимальный вес, который можно померять набором 1+3+9+27+81 = 121.

Но почему не может быть набора из четырёх грузов? Вроде бы тоже просто. Комбинации четырёх грузов могут быть только… Пусть a,b,c,d — по понижению веса груза. Подсчитаем все возможные комбинации. Грузы могут быть с плюсом, минусом или отсутствовать. Итого количество комбинаций = 3*3*3*3 = 81. Сотню никак не покрыть.

Есть ещё одно универсальное и очень красивое решение, вот такое:

Применяем троичную систему счисления. Любое число в троичной системе может быть представлено как разность чисел, состоящих только их 0 и 1, причём единицы в обоих числах стоят на разных позициях (почему так? — это просто, попробуйте сами). То есть, если нам надо решить задачу с весами и гирями для произвольного N, то это число надо записать в троичной системе. Сколько будет знаков — столько и гирь потребуется.

Задачка 4. ЖЖ-блогер находится в лодке в центре круглого озера радиусом 1. На берегу — гоблин, жаждущий съесть несчастного блогера. К счастью, гоблин может двигаться только по берегу. К несчастью, его скорость превосходит скорость лодки в 4 раза. Всё, что нужно для спасения, — добраться до берега, не попав в лапы гоблина. Получится ли? Бегает блогер быстрее гоблина, главное – оказаться на берегу на расстоянии от него.

Зависит от выбора стратегии. Если будет действовать умно, то убежит.

Блогер может плыть как и куда угодно внутри четверти радиуса от центра — здесь он может относительно центра быть быстрее гоблина и оказаться с ним в противоположных точках относительно центра озера. Оставшуюся часть ему надо плыть по минимальному пути (напрямую к краю), любое отклонение лишь приближает гоблина. Итого, оптимум (когда они одновременно достигают одной точки)… Гоблину бежать половину круга, блогеру плыть от четверти радиуса r до края. N – во сколько раз быстрее должен быть гоблин, v – скорость лодки:

Время t = π*r / (N * v) = (3/4 * r ) / v

Сокращаем:

π = N*(3/4)
N = 4/3 * π = 4.188790… и так далее.

Блогер плывёт на лодке в 4 раза медленнее гоблина => гоблин остался без ужина.

Всё на этом.

И снова поздравляю mikluha_maklai с правильным решением всех задачек!

А заодно ответ на тот самый мега-судоку, который, похоже, никто так и не осилил. Он чрезвычайно тяжёлый, но решается. Причём есть единственное решение. Вот оно:

Причём шёл я к решению с перерывами без малого 20 дней, проверив несколько десятков вариантов.

Вот такая мега-супер-судока :) Было бы интересно увидеть оптимальное решение — за минимум ветвлений и переборов. Но это уже работа для компьютера.

Всё на этом на сегодня, всем до следующих задачек!