Страниц: 1 [2]
  Печать  
Автор Тема: Найдите максимальное N  (Прочитано 9732 раз)
0 Пользователей и 1 Гость смотрят эту тему.

Задачу придумал сам - навеяло. Является по сути компиляцией нескольких задач Smiley
У Шаха М мудрецов и он решил узнать насколько они умны.
Он собрал их и показал им образцы колпаков К разных цветов (К<М).
Он сказал что каждому мудрецу будет надет колпак с одним из этих К цветов, каждый мудрец будет видеть колпаки других.
Будут использованы все цвета.
Все мудрецы будут сидеть в одном зале и смотреть друг на друга. Ни говорить, ни жестикулировать нельзя.
Те, из мудрецов, которые готовы назвать свой цвет, могут молча выйти из Зала и назвать свои цвета Шахине, которая зафиксирует ответ. А Шах будет сидеть в зале и засечёт время по Главным часам шахства, которые тоже в зале и видны всем.
Часы - обычные цифровые часы с часами и минутами.
Мудрецам предлагается посовещаться между собой некоторое время, после чего процедура начнётся и пойдёт отсчёт времени.
Смогут ли мудрецы определить цвет своего колпака?
Соображают они очень и очень быстро.

zhekas
Гений-Говорун
*
Offline Offline

Сообщений: 1035

СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486



Просмотр профиля Email
Ответ #15 : Август 08, 2013, 16:47:57 �

Так: я на первом взвешивании взвешиваю 33 и 33 монеты (3X и 3X). В случае их неравенства
проверяю кучку 3X с фальш.
Тоесть получается так. Ты взвешиваешь 33 и 33 и не взвешиваешь ещё 33?
Записан
Руслан Дехтярь
Гость
Ответ #16 : Август 08, 2013, 16:52:32 �

У меня монет всего( 33 + 33, 27 +27, 21 + 21, 15 +15, 27, 9, 3)
я проверяю 33 и 33.
в случае 1 - го неравенства 11 и 11 и заодно 11, которые отложил.
Записан
zhekas
Гений-Говорун
*
Offline Offline

Сообщений: 1035

СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486



Просмотр профиля Email
Ответ #17 : Август 08, 2013, 16:56:15 �


в случае 1 - го неравенства 11 и 11 и заодно 11, которые отложил.
А почему ты откладываешь столь же, сколько и взвешиваешь? Ведь если у тебя взвешенные кучки будут равными по весу, то ты возмешь всё теже 11, но на один неравный ход у тебя будут больше.

Тоесть у тебя получилось приемущество на один неравный ход, но ты им не пользуешься, так берёшь всё теже 11 монет
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #18 : Август 09, 2013, 06:14:15 �

buka
а васне смущает вот это условие?
Цитировать
Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний
Нет, не смущает.
Итак, в общем случае: нам надо найти максимальное N монет, среди которых одна фальшивая, причём весы ломаются после Х взвешиваний где неравенство и за не более чем К взвешиваний.
То есть, нам надо найти N как функцию Х и К (у Вас - Х=3,K=7)
Если Х = 1, то N(X,K) = N(1,K) = 2K+1. С этим, думаю, ясно.
Если Х = 2, то N(X,K) = N(2,K) = 2*(N(1,K-1)+N(1,K-2)+...+N(1,2)+31
Если Х = 3, то N(X,K) = N(3,K) = 2*(N(2,K-1)+N(2,K-2)+...+N(2,3))+32
Рекурсивно:
N(X,K) = 2*(N(X-1,K-1)+N(X-1,K-2)+...+N(X-1,X))+3X-1
Записан
Руслан Дехтярь
Гость
Ответ #19 : Август 09, 2013, 08:24:36 �


в случае 1 - го неравенства 11 и 11 и заодно 11, которые отложил.
А почему ты откладываешь столь же, сколько и взвешиваешь? Ведь если у тебя взвешенные кучки будут равными по весу, то ты возмешь всё теже 11, но на один неравный ход у тебя будут больше.

Тоесть у тебя получилось приемущество на один неравный ход, но ты им не пользуешься, так берёшь всё теже 11 монет
Ну а если весы покажут неравенство на втором взвешивании и это уже 2-е неравенство? Если в кучках будет больше чем 11 монет, не хватит просто ходов, чтобы за оставшиеся 5 взвешиваний взвесить.
Или я что- то не понимаю?
Записан
zhekas
Гений-Говорун
*
Offline Offline

Сообщений: 1035

СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486



Просмотр профиля Email
Ответ #20 : Август 09, 2013, 09:06:30 �


в случае 1 - го неравенства 11 и 11 и заодно 11, которые отложил.
А почему ты откладываешь столь же, сколько и взвешиваешь? Ведь если у тебя взвешенные кучки будут равными по весу, то ты возмешь всё теже 11, но на один неравный ход у тебя будут больше.

Тоесть у тебя получилось приемущество на один неравный ход, но ты им не пользуешься, так берёшь всё теже 11 монет
Ну а если весы покажут неравенство на втором взвешивании и это уже 2-е неравенство? Если в кучках будет больше чем 11 монет, не хватит просто ходов, чтобы за оставшиеся 5 взвешиваний взвесить.
Или я что- то не понимаю?
Ну дак кто межает взвешивать всё теже 11, а откладывать (не взвешивать) больше
Записан
Страниц: 1 [2]
  Печать  
 
Перейти в: