В поезд сели люди занимая места-верхнее или нижнее, но возможно, что не было никого на верхних или нижних полках. Проводница у каждого спросила:"среди остальных пассажиров вагона сколько человек едут на нижней полке?". Все дали верный ответ. Проводница сложила все ответы и получила число 42. Найди разницу между числом пассажиров, едущих сверху и снизу, если никто не назвал число меньше 3
Вопрос Булоса: «Означает ли „da“ „да“, если и только если ты бог правды, а бог B — бог случая?». Другой вариант вопроса: «Является ли нечётным число истинных утверждений в следующем списке: ты — бог лжи, „ja“ означает „да“, B — бог случая?»
Решение задачи может быть упрощено, если использовать условные высказывания, противоречащие фактам (counterfactuals)[4][5]. Идея этого решения состоит в том, что на любой вопрос Q, требующий ответа «да» либо «нет», заданный богу правды или богу лжи:
Если я с тебя Q, ты ответишь «ja»?
ответом будет «ja», если верный ответ на вопрос Q это «да», и «da», если верный ответ «нет». Для доказательства этого можно рассмотреть восемь возможных вариантов, предложенных самим Булосом.
Предположим, что «ja» обозначает «да», а «da» обозначает «нет»:Мы спрашивали у бога правды, и он ответил «ja». Поскольку он говорит правду и верный ответ на вопрос Q — «ja», оно обозначает «да».Мы спрашивали у бога правды, и он ответил «da». Поскольку он говорит правду и верный ответ на вопрос Q — «da», оно обозначает «нет».Мы спрашивали у бога лжи, и он ответил «ja». Поскольку он всегда лжёт, поэтому на вопрос Q он ответит «da». То есть правильный ответ на вопрос «ja», который обозначает «да».Мы спрашивали у бога лжи, и он ответил «da». Поскольку он всегда лжёт, поэтому на вопрос Q он ответит «ja». То есть правильный ответ на вопрос «da», который обозначает «нет».Предположим, что «ja» обозначает «нет», а «da» обозначает «да»:Мы спрашивали у бога правды, и он ответил «ja». Поскольку он говорит правду и верный ответ на вопрос Q — «da», оно обозначает «да».Мы спрашивали у бога правды, и он ответил «da». Поскольку он говорит правду и верный ответ на вопрос Q — «ja», оно обозначает «нет».Мы спрашивали у бога лжи, и он ответил «ja». Поскольку он всегда лжёт, поэтому на вопрос Q он отвечает «ja». Но, так как он лжёт, верный ответ на вопрос Q — «da», что означает «да».Мы спрашивали у бога лжи, и он ответил «da». Поскольку он всегда лжёт, поэтому на вопрос Q он отвечает «da». Но, так как он лжёт, верный ответ на вопрос Q — «ja», что означает «нет».
Используя этот факт, можно задавать вопросы:[4]
Спросим бога B: «Если я с у тебя „Бог А — бог случая?“, ты ответишь „ja“?». Если бог B отвечает «ja», значит, либо он бог случая (и отвечает случайным образом), либо он не бог случая, а на самом деле бог A — бог случая. В любом варианте, бог C — это не бог случая. Если же B отвечает «da», то либо он бог случая (и отвечает случайным образом), либо B не бог случая, что означает, что бог А — тоже не бог случая. В любом варианте, бог A — это не бог случая.Спросим у бога, который не является богом случая (по результатам предыдущего вопроса, либо A, либо C): «Если я с у тебя: „ты - бог лжи?“, ты ответишь „ja“?». Поскольку он не бог случая, ответ «da» обозначает, что он бог правды, а ответ «ja» обозначает, что он бог лжи.Спросим у этого же бога «Если я у тебя с Бог B — бог случая?“, ответишь ли ты „ja“?». Если ответ «ja» — бог B является богом случая, если ответ «da», то бог, с которым ещё не говорили, является богом случая.
Оставшийся бог определяется методом исключения.
Можно подумать про принцип формирования таких чисел.
1) Пусть число не оканчивается на 9. Тогда изначально сумма его цифр была S, кратная 13. Затем она стала S+1, которая уже не кратна 13. Отсюда делаем вывод, что число должно обязательно оканчиваться на 9.
2) Теперь определим, на сколько же девяток должно оканчиваться это число. Разобьем число на две части: префикс и суффикс. Суффикс полностью состоит из девяток. Пусть суффикс длины n.Тогда сумма цифр в суффиксе равна 9n. Теперь пусть сумма цифр в префиксе равна S. (Разберем разбиение на примере любого числа. Возьмем, например, 1234439999. Сумма префикса S=1+2+3+4+4+3=17, сумма суффикса равна 9*4=36.)
Тогда происходят такие вещи:
а) Сначала сумма цифр равна S + 9n. По условию, она кратна 13. Тогда S +9n = 13a, где a - некоторое целое и большее нуля число.
б) Теперь прибавляем к этому числу 1. После этого действия сумма в префиксе увеличивается на 1, а сумма в суффиксе становится равна 0, так как суффикс полностью состоит из девяток. Новое равенство: S+1 + 0*n = 13b, где b - некоторое целое и большее нуля число.
Имеем систему уравнений:
S +9n = 13a,
S + 1 = 13b
Переменных больше, чем уравнений, значит, число решений бесконечно много.
Из первого уравнения вычтем второе, получим:
9n-1=13(a-b)
n = (13 (a - b) + 1) / 9 = (4 (a - b) + 1) / 9 + a - b
Тогда можно подобрать такие пары чисел a и b, где a > b, что n будет целым числом. Пусть a - b = q, тогда n = (4q + 1) / 9 + q, а 4q+1 должно быть кратно 9.
Это значит, что 4q+1=9A, где A-целое.
4q=9A-1
q = (9A-1) / 4 = (4 * 2A + A - 1) / 4 = 2A + (A-1)/4
Отсюда видно, что A-1 должно быть кратно 4.
Тогда A-1 = 4B, где B - некоторое целое число, больше или равное 0.
Тогда A = 4B+1 - уже ограничений на делимость нет. Поэтому можно вернуться к переменным, введенным ранее.
q = (9 * (4B+1) - 1) / 4 = 9B + 2.
n = (4q + 1)/9 + 2q = (4 * (9B + 2) + 1) / 9 + 9B + 2 = 13B + 3
a = b + 9B + 2.
S = 13b - 1
Теперь уже смело можно выбирать целые числа b и B, чтобы определить a. После определения a однозначно определятся n и S. Тогда уже, зная n и S, можно выписать множество чисел, обладающих свойствами, указанными в условии.
Вот пример, если запутались:
Пусть b = 3, B = 1. Тогда:
a = 1 + 9*1 + 2 = 12.
S = 13b - 1 = 13*3 - 1 = 38,
n = 13B + 3 = 13*1 + 3 = 16
При таких параметрах получится число, например, такое:
7878719999999999999999.