Тема: Логические загадки - 5

[Erlom-Tiu›]

Очередная серия.  
Текущие задачи:

1а.(Maeglor)
Даны 12 монет, среди них одна фальшивая (легче она или тяжелее - неизвестно).
Найти ее за три взвешивания.

1б. (Maeglor)
Для предыдущей задачи рассмотреть случай N монет (N>2, фальшивая только одна)

1в. (E-T)
Условия те же, 3 взвешивания, но монет - 13 :-)


               

               

[Арвинд›]

Erlom-Tiu, а была уже задача про монеты. Не помнишь?

Про 17/18 тоже была. Про Алису и Громозеку - как минимум два человека здесь решили, но решения написано не было. Если кому надо, пущай Erlom-Tiu напишет. Ну или я могу.

               

               

[Maeglor›]

Для 13 монет за 3 взвешивания готов доказать невозможность

               

               

[Maeglor›]

Цитата из: Арвинд on 11-11-2003, 14:49:32
Erlom-Tiu, а была уже задача про монеты. Не помнишь?



А вот общего случая не ставилось.

Повторю вопрос
Найти зависимость минимального количества взвешиваний от числа монет(>=3)
необходимых для определения фальшивки отличной массы (не извесно тяжелее или легче)

               

               

[Kэt›]

А зря, для 13 можно (одна монета во взвешиваниях не участвует), только нельзя сказать, легче монета, или тяжелее.

               

               

[Maeglor›]

А я о чем?

               

               

[azyam›]

2Maeglor в условие не сказано определить тяжелей она или легче, сказано просто найти ее, а для 13 монет с 3мя взвешаниями можно ее найти.

               

               

[Арвинд›]

Цитата из: Maeglor on 11-11-2003, 23:56:40

Цитата из: Арвинд on 11-11-2003, 14:49:32
Erlom-Tiu, а была уже задача про монеты. Не помнишь?

А вот общего случая не ставилось.


Насколько я помню, тогда I_3am дал ссылку на статью, где рассматривалась эта задача. В том числе и общий случай. Оно, конечно, не по правилам - но ссылка там до сих пор висит, не стирать же ее теперь. Думаю, нет смысла возвращаться к задаче, решение которой может прочесть любой, кто пройдется по тредам "Логические задачи" этого форума.

               

               

[Арвинд›]

Похоже, здесь нет новой задачи?

Тогда для разминки вытащу из заначки одну, несложную.

Сто людоедов приехали на пир. И трапеза людоедов была обильна и сытна: обедающий людоед проглатывает целиком себе подобного (игнорируя совет тщательно пережевывать пищу). Пообедавший людоед, конечно, может и сам сослужить обедом для другого своего собрата. Так и составляются пищевые цепочки. Длиной цепочки назовем количество людоедов, вложенных друг в друга.
Вопрос: какой максимальной длины цепочка точно присутствует, если известно, что какие бы десять людоедов мы не взяли, среди них найдутся два экземпляра, один из которых покоится в желудке другого?

               

               

[azyam›]

основываясь на несложности, рискну предположить, что 18, так как в 19 можно вложить 10 людоедов не вложенных друг в друга

               

               

[azyam›]

решение с другого конца
очевидно рядов не больше 9
очевидно при девяти рядах нельзя использовать цепочку больше 2х


а вот тут у меня возник вопрос, транзитивность тут поддерживается?
т.е. если a съел б, б съел с, то a съел с.
если поддерживается,то максимальная цепочка = 100

если нет, то мне кажется, что расклад невозможен, но пока еще думаю

               

               

[Арвинд›]

Azyam, я и впрямь написал не очень корректно, исправляюсь.

В последнем условии (найдутся два, один из которых в желудке другого) имеется в виду, конечно, что может быть не непосредственное проглатывание. Т.е. транзитивность для этого условия имеет место быть.

Максимально возможная цепочка при этом будет, разумеется, 100. Но вопрос был - какая максимальная цепочка будет гарантированно? Говоря мат. языком - указать минимакс.


               

               

[Vantela›]

ай ай ай
ничерта не понял.....
а вот если у нас три людоеда(действующих то есть не проглоченных)
прочем в 3х из них находится по 3и

итого в тазком варианте получится что их 12 со всеми вложенными
и можем мы вщять 10 из них?

               

               

[azyam›]

Цитата из: Арвинд on 13-11-2003, 00:41:57
Вопрос: какой максимальной длины цепочка точно присутствует, если известно, что какие бы десять людоедов мы не взяли, среди них найдутся два экземпляра, один из которых покоится в желудке другого?


чувствую, что два не зря выделено, что это означает: найдутся как минимум два? или ровно два?
подумал и принял решение, что ровно два здесь не подходит

а минимакс из чего?

               

               

[Арвинд›]

Vantela, извините, но я Вас не понимаю, и поэтому ничего ответить не могу  

Цитата из: azyam on 13-11-2003, 14:18:09
а минимакс из чего?

Условиям задачи могут удовлетворять самые разные расклады. В каждом раскладе берется максимум длины цепочек. По всем раскладам берется минимум этих максимумов. Теперь понятно написано?
Попробую еще так: среди каждых десяти мы можем указать по крайней мере двух людоедов, вложенных друг в друга, значит, среди всех ста людоедов цепочка длины 2 найдется всегда. Вопрос: а какой наибольшей длины цепочка есть всегда?


               

               

[azyam›]

тогда 12

               

               

[Vantela›]

пусть будет минимум.... как бы людоеды едят по минимому
есть 9 людоедов которые не ели вообще никого.....
а теперь эту девятку бедут зверски лопать.....
тогда получится что еще 9 сьели их
и тд

получим 9 "никем не сьеденых" которые ели других
каждая цепочка будет длинной 11 (1-2-3-4-5-6-7-8-9-10-11 ---- по вложенности и так 9 раз)
останется еще один голодный которого никто не ел и он кникого не ел

он для выполнения усл -----  одну из цепочек

итого 12 макс цепочка

ЗЫ как теперь?

ЗЫЫ черт до меня уже кто то решил....

               

               

[Erlom-Tiu›]

Действительно 12.
(кратко - из принципа Дирихле ~= предыдущее сообщение)

В свете обобщений: будем рассматривать случай?  когда всего N людоедов, среди любых k найдутся хотя бы двое "вложенных"?

по взвешиванию: да, именно в той статье по ссылке I_3am-a и выводится формула, приведённая Кэt

               

               

[azyam›]

если N/(k-1) делится нацело, то N/(k-1), иначе N/(k-1)+1

               

               

[Erlom-Tiu›]

понял. В смысле целая часть(N/(k-1))+1.