Задача о 100 узниках.

Начальник тюрьмы предлагает 100 узникам,приговоренным к смертной казни последний шанс,Узники пронумерованы от 1 до 100.В тюрьме 25 камер,В каждой камере по два узника к левой стене прикованы кандалами и по два узника прикованы кандалами к правой стене.Начальник тюрьмы говорит,

-Я на всю ночь оставляю Вас не прикованными,Вы можете меняться местами как угодно,но утром надзиратель закрепит кандалы на каждом из Вас и я зайду в первую камеру,перемножу номера двух узников с левой стены,перемножу номера двух узников с правой стены и сложу полученные произведения, и тоже самое я проделаю во всех 25 камерах.Если во всех 25 камерах полученные числа будут одинаковы,все будут свободны, так что все в Ваших головах,которые если не справятся,Вам уже и не

нужны будут.

1 эксперт согласен

Артём Ромашов

8 мар 2023

Жаль смертников.

Андрей Саускан

8 мар 2023

@Артём Ромашов, Ничего, может начальник плохо умножает и складывает.

Андрей Бахматов

10 мар 2023

Предварительная выкладка. Напрашивается искать минималистичное решение, при котором в каждой камере будет действовать один и тот же принцип. Задача – сформировать сумму произведений x*y(x)+z(x)*t(x), где y, z, t – линейные функции от x таким образом, чтобы после раскрытия коэффициенты при неизвестных были нулевыми. Избавимся сначала от второй степени: x(a–x)+(b+x)(c+x). Затем от первой степени: x(a–x)+(x–b)(x–(a–b)), после раскрытия получается константа b(a–b). Осталось подобрать a и b таким образом, чтобы каждое из выражений x, a–x, x–b, x–(a–b) находилось в своём диапазоне: [1;25], [26;50], [51;75] или [76;100]. Увы, здесь вариантов нет: даже если направление выбрано верно, сам вариант завёл в тупик. Возможно, получится при рассмотрении камер не по одной, а по пять.

Андрей Саускан

10 мар 2023

@Андрей Бахматов, У Вас более комплексный подход,чем у меня,я нашел одно нужное разрешение по одной камере,но есть интуитивная уверенность,что нужных разрешений как по одной камере,так и по пять существует много,но как получать решения в комплексе,я не знаю, и еще абсолютно не уверен,что есть какой-то переброс с этой задачи на задачу 100!+1,ведь эту задачу Тантона для частного случая 100!+1. можно несколько переформулировать.Возьмем 100!,Разложим его на простые множители.Каким образом нужно распределить все присутствующие в разложении множители на две группы,чтобы после перемножения чисел в первой группе и перемножения чисел во второй группе,разница полученных произведений была минимальной?Если каким-то образом доказать,что минимальная разница равна какому-то числу,больше чем 2,то это автоматом докажет невозможность целочисленного квадрата равного 100!+1.

Сергей Леонтьев

12 мар 2023

Если я правильно понял, то имеются шансы на счастливый конец:

1*35 + 47*95 = 4500
2*94 + 49*88
3*28 + 46*96
4*85 + 64*65
5*9 + 55*81
6*99 + 62*63
7*59 + 61*67
8*26 + 58*74
10*70 + 38*100
11*14 + 53*82
12*27 + 48*87
13*97 + 41*79
15*80 + 44*75
16*73 + 34*98
17*71 + 37*89
18*52 + 54*66
19*92 + 32*86
20*72 + 45*68
21*77 + 31*93
22*56 + 43*76
23*91 + 29*83
24*51 + 42*78
25*84 + 40*60
30*90 + 36*50
33*69 + 39*57 = 4500

Причём вариант суммы 4500 не единственный, есть ещё несколько возможных сумм.

…что есть какой-то переброс с этой задачи на задачу 100!+1, ведь эту задачу Тантона для частного случая 100!+1. можно несколько переформулировать.Возьмем 100!,Разложим его на простые множители.Каким образом нужно распределить все присутствующие в разложении множители на две группы,чтобы после перемножения чисел в первой группе и перемножения чисел во второй группе,разница полученных произведений была минимальной?Если каким-то образом доказать,что минимальная разница равна какому-то числу,больше чем 2,то это автоматом докажет невозможность целочисленного квадрата равного 100!+1.

А вот этого замечания я не очень понял (ну, или я неправильно прочитал условие задачи).

Андрей Саускан

12 мар 2023

@Сергей Леонтьев, Замечательно! Вы все правильно поняли. У меня получилась другая сумма,5150. А насчет этого замечания,я сам не очень понимаю,если простыми словами.то примерно так.Например 8! при разложении на простые множители и разделении на две группы,минимальная разница между произведением чисел в одной группе и в другой не может быть меньше 18,значит 8!+1 не может быть квадратом целого числа.а есть ли какой-нибудь переход между получением наименьшего числа для 100 чисел и тем разрешением.что Вы нашли.понятия не имею.То есть вопрос такой.Нельзя ли попытаться найти какую-нибудь числовую закономерность между тем.что Вы нашли и разложением на две группы с наименьшей разницей? Выглядит очень неправдоподобно и наверное не разрешимо. Благодарю за Ваш ответ.