![](/media/images/top/preview/icpicslivejournalcome_kaspersky2497748788867668886766_original.jpg)
Правдорубы vs лжецы.
![топ 100 блогов](/media/images/default.jpg)
А чтобы они, будни, получились совсем весёлыми, у меня есть для вас хорошая задачка :) Не пугайтесь! – в этот раз она не вполне арифметическая. Она логическая и социальная. Про то, как, наплевав на карантины и пандемии, большая толпа из тридцати друзей и просто знакомых собралась на шашлыки с пивом. Они расселись за большой стол и... вдруг оказалось, что среди них есть обманщики! А очень хочется найти кого-то абсолютно честного, чтобы не пропасть здесь навсегда. Для этого им можно задавать вопросы. Однако, количество вопросов ограничено, и вопрос можно задать только один.
Короче, вот вам задачка на подумать про деформацию социального поведения в условиях ограничений свободы выбора проведения летнего отпуска :)
Условие:
За круглым столом сидит компания из тридцати человек. Каждый из них либо лжец, либо правдоруб. Всех сидящих спрашивают: Кто Ваш сосед справа – правдоруб или лжец? (они знают друг друга и кто есть кто). В ответ правдоруб всегда говорит только правду, а лжец может сказать как правду, так и солгать. Известно, что количество лжецов не превосходит X.
Вопрос:
При каком наибольшем значении X всегда можно, зная ответы от всей компании, указать на правдоруба в этой компании? На любого правдоруба, произвольного?
![Правдорубы vs лжецы. demotivatorium_ru_tjajelaja_matematika_122200 Правдорубы vs лжецы. demotivatorium_ru_tjajelaja_matematika_122200](https://ic.pics.livejournal.com/e_kaspersky/24977487/8886766/8886766_original.jpg)
А теперь ответы на прошлую порцию задачек и позывные владельцев талантливых мозгов, решивших её.
Задачка-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, Ведро Помоев (ещё бы ник поменять :),
![Правдорубы vs лжецы. Правдорубы vs лжецы.](/images/main/pravdorubi-vs-ljeci-667fb2.jpg?from=https://l-stat.livejournal.net/img/userinfo_v8.png?v=17080?v=410.2)
|
</> |
![](/media/images/top/preview/icpicslivejournalcome_kaspersky2497748788867668886766_original.jpg)