|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
11.03.2013, 16:44 | #611 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Sibedir, эту задачу сам не решал (скорее всего и не решил бы), но решение когда-то видел - там много (очень много) рассуждений для тривиального частного случая с выводом формулы и обобщения её на 100 зк Подсказка желающим решить - проанализировать случай 3зк и номера от 1 до 3.
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 11.03.2013 в 16:47. |
11.03.2013, 17:04 | #612 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Тюремщик подслушивает разговоры заключённых и пытается подобрать номера так, чтобы они проиграли. Каждый ответ - функция от значений на остальных шляпах. Имеем N неравенств вида Fk(a1, a2, ..., a(k-1), a(k+1), ..., an)-ak != 0 (1 <= ai <= N). Требуется сделать так, чтобы эта система была неразрешима. И теперь мы понимаем, что это элементарно: достаточно взять Fk=((-a1-a2-...-a(k-1)-a(k+1)-...-an+k) mod N) + 1. Действительно, если (a1+a2+...+an) mod N + 1=s, то Fs=0. |
|
11.03.2013, 17:19 | #613 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
11.03.2013, 17:27 | #614 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
Да, как-то так.
Ну я не всё понял про ak !, но тоже понравилось. |
11.03.2013, 17:38 | #615 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Sibedir, это !=, символ "не равно" из C. Аналог <> в Pascal.
|
11.03.2013, 20:45 | #616 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Sibedir, респект за задачу.. Я так ничего и не смог придумать..
А можно вопрос : что такое Fk ? |
11.03.2013, 21:34 | #617 |
Раздолбайских Дел
Старожил
Регистрация: 22.05.2009
Сообщений: 3,828
|
Шляпы же не меняются? Один зэк называет первое увиденное число, все остальные его повторяют... брутфорс...
Alar, верни репу!
|
11.03.2013, 21:36 | #618 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
|
|
11.03.2013, 21:59 | #619 | ||
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Если перевести обратно в термины задачи, то заключённые считаются по порядку, от 0 до 99, и каждый запоминает свой номер. После этого, когда им надевают шляпы (пусть числа на шляпах тоже от 0 до 99), каждый складывает числа на шляпах всех прочих, берёт минус получившуюся сумму, прибавляет свой номер и берёт результат по модулю 100. Пусть сумма всех чисел на шляпах равна s. Тогда заключённый номер (s mod 100) назовёт своё число x правильно: при подсчёте чужих шляп он получит сумму s-x, с минусом это будет x-s, после прибавления своего номера и взятия результата по модулю 100 останется x, ура. Остаётся только внести поправки на то, что номера не от 0 до 99, а от 1 до 100. И, разумеется, приходится надеяться, что все 100 заключённых в состоянии правильно сложить в уме 99 двузначных чисел... Цитата:
Последний раз редактировалось Abstraction; 11.03.2013 в 22:03. |
||
11.03.2013, 22:07 | #620 |
Раздолбайских Дел
Старожил
Регистрация: 22.05.2009
Сообщений: 3,828
|
пардон муа... тогда может по порядку?)
Alar, верни репу!
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
интересные проги | kipish | Софт | 85 | 18.12.2022 01:03 |
Текст на картинках | SunLight | Microsoft Office Word | 2 | 08.08.2007 12:59 |