Правдорубы vs лжецы.

Всем приятных трудовых будней!

А чтобы они, будни, получились совсем весёлыми, у меня есть для вас хорошая задачка :) Не пугайтесь! – в этот раз она не вполне арифметическая. Она логическая и социальная. Про то, как, наплевав на карантины и пандемии, большая толпа из тридцати друзей и просто знакомых собралась на шашлыки с пивом. Они расселись за большой стол и… вдруг оказалось, что среди них есть обманщики! А очень хочется найти кого-то абсолютно честного, чтобы не пропасть здесь навсегда. Для этого им можно задавать вопросы. Однако, количество вопросов ограничено, и вопрос можно задать только один.

Короче, вот вам задачка на подумать про деформацию социального поведения в условиях ограничений свободы выбора проведения летнего отпуска :)

Условие:

За круглым столом сидит компания из тридцати человек. Каждый из них либо лжец, либо правдоруб. Всех сидящих спрашивают: Кто Ваш сосед справа – правдоруб или лжец? (они знают друг друга и кто есть кто). В ответ правдоруб всегда говорит только правду, а лжец может сказать как правду, так и солгать. Известно, что количество лжецов не превосходит X.

Вопрос:

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

А теперь ответы на прошлую порцию задачек и позывные владельцев талантливых мозгов, решивших её.

Задачка-1. Доказать, что сумма двух последовательных простых чисел больше тройки раскладывается как минимум на три множителя.

Решение: Сумма двух простых больше тройки = чётное число, т.е. один множитель = 2. Разделим сумму на двойку, получим какое-то число посередине между парой простых. Поскольку это число не может быть простым по условию задачки, то оно имеет как минимум два делителя (помимо 1 и себя). Всё.

Задачка-2. 1! + 2! + 3! + … + x! = y^2, надо найти все x и y.

Решение:
1! = 1 x,y = (1,1).
1!+2! = 3
1!+2!+3! = 9 x,y = (3,3).
1!+2!+3!+4! = 33
5! = 120, все дальнейшие факториалы заканчиваются на ноль, т.е. сумма всех факториалов от 4 и далее заканчивается на тройку. Но нет таких квадратов, которые заканчиваются на три. Т.е. больше решений нет.

Задачка-3. Для всех чисел от 01 до 99 доказать (или опровергнуть), что существует другое число, произведение с которым состоит только из единиц и нулей – и показать способ его поиска. Все числа натуральные, система счисления 10-тичная (уточняю: 10=десятичная).

Решение: То, что такое число существует – очевидно из задачки прошлого раза, где надо было доказать существование такого числа, делящегося на 17. Надо просто выписать все числа типа ‘1’, ’11’, … ‘1…11’ (99 единиц) и последовательно делить их с остатком на произвольные n от 1 до 99. Рано или поздно они либо дадут остаток ноль (т.е. делится), либо одинаковые отстатки. Тогда меньшее ‘1…11’-число вычитаем из большего – вот оно, которое делится на n.

Теперь как найти такое число. Метод поиска был предложен там же: надо последовательно умножать n на такие комбинации, которые в результате будут подставлять 0 или 1 в конец произведения. Цикл этот можно раскручивать бесконечно, но если надоест, то его можно закончить за конечное число действий.

Задачка-4. Доказать, что если число, состоящее только из единиц (111….111) делится на 2017, то оно делится и на 9. И найти минимальное такое число.

Решение: Во-первых, такое число существует. Берём все ‘1-1’-числа аналогично предыдущей задачке и получаем некое ‘1…10…0’, которое делится на 2017. Но поскольку 2017 – простое, то старшая часть с единицами делится на 2017.

Во-вторых, применяем тяжелую артиллерию в виде Малой Теоремы Ферма, которая гласит, что если ‘p’ — простое число и ‘a’ — целое число, не делящееся на ‘p’, то ->

a^(p−1) ≡ 1 (mod p)

откуда тут же следует, что число из 2016 единиц делится на 2017. А поскольку в этом числе 2016 единиц, а 2+1+6=9 — то это же признак делимости на девять! То есть, 2016 единиц делятся на 2017 и на 9.

А в-третьих, доказать минимальность этого числа у меня просто и доступно никак не получилось. Пришлось считать перебором по делителям 2016 :( Чуть арифмометр не сломал :) Хотя, наверное, в данном случае можно было и программку написать.

А теперь время восхищения и аплодисментов! C задачками справились: Gr Bear, Ведро Помоев (ещё бы ник поменять :), (особое «ку» за алгоритм нулей и единиц). Поздравляю!