Логические задачи : 30 одинаковых таблеток

	"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.
Задачи на логику и сообразительность
Главная \| О проекте \| Все задачи-1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C \| Добавить задачу

О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Поиск на сайте

запомнить меня

Задачи

Переливания и взвешивания

Теорвер, комбинаторика

Задания на наблюдательность

требуется помощь

Чисто поржать

Детские с подковыркой

Данетки

Текущие:

  Мой любимый грех (с)
  Математика в архитектуре
  Не сыпь мне соль на рану
  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

Разгаданные недавно:

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!

Справочная

Признаки делимости
Площади фигур

Реклама

Версия для смартфонов

задача: 30 одинаковых таблеток

Задачу прислал: Александр Ковальджи

По кругу выкладывают 30 одинаковых на вид таблеток, из них 20 хороших и 10 плохих. Два мудреца по очереди берут по одной таблетке. Первый мудрец будет знать, где лежат плохие таблетки, а второй – нет. Мудрецы хотят до выкладывания таблеток договориться, как после каждого хода первого второй найдёт хорошую таблетку. После 20 ходов на столе должны остаться 10 плохих таблеток. Предложите алгоритм действий для мудрецов. (Беря таблетки, мудрецы не общаются и не подают никаких знаков. Каждый видит, какую таблетку взял партнёр.)


+ 6 -

Ответ

Решение задачи

Ваши ответы на задачу

ответов: 13

K2 2019-04-05 12:00:54 пишет:

Так... Дирихле это клетки и кролики? Ну не важно, я про другое:
- при любом изменении ххпххпххпххп... появится хотя бы одна группа с больше чем 2х - хотя и это не то.
- ну да ОКРВВЕРХ( Ν(х)/N(п) ) - это минимальный размер максимальной группы, ведь так? У нас это 2.
Раз так - то у нас всегда есть как минимум одно ХХ - которое слева рано или поздно закончится П. Там на их стыке и появится требуёмое ПХХ.
Вот теперь наверное всё.

K2 2019-04-05 11:49:52 пишет:

Влезу? :)

1 - для доказательства существования группы (кстаи, по идее же нас Любая из трёх возможных устроит? в принципе?) - если расположения НЕ равномерны то есть более плотные "участки" - и на более плотных очевидно будет или ПП или ПХП - и от той и от другой смело оставляем только П - и концентрация Х только увеличится, пока не выбросим все "переконцентрированные" участки, в крайнем случае пока не останется только одно П и всё остальное Х = группа ПХХ - есть... Да... вариант ХПХ - не годится -- не сможем им разбирать группы ПП - значит выбор только из двух - там можно сказать симметрично.

2 - Про память. Надо запомнить всего лишь 10 положений, при чём по мере "игры" - будет всё больше просветов-ориентиров, что-то ещё и в группы объединится, а после восьмой - можно и вовсе переключиться на 6 оставшихся и запоминать только их. 8 - вроде бы уже не очень много, тем более что тут Мудрецы...

А ещё в условиях нет запрета помечать что-то у себя в блокноте или на салфетке - главное что бы другому этого не было видно, да и то, в данном случае "другому" = Первому это и не интересно, он и так их знает. (да ещё кстати как-то и Помнит)

ivana2000 2019-04-05 10:59:34 пишет:

«ivana2000, а если, что-то типа:
ПХПХПХПХПХПХПХПХПХПХХХХХХХХХХХ»

Это одна из возможных начальных комбинаций. Для наглядности можно записать ее так:
пхпхпхпхпхпхпхпхпхПХХххххххххх.
Первый берет среднюю «Х» из группы «ПХХ», второй – следующую против часовой стрелки (т.е. как изначально договорятся). Оставшуюся в группе «П» сдвигают куда-то на столе. Остается:
пхпхпхпхпхпхпхпхпхххххххххх+П
пхпхпхпхпхпхпхпхПХХхххххххх+П
пхпхпхпхпхпхпхпххххххххх+ПП
пхпхпхпхпхпхпхПХХххххххх+ПП
пхпхпхпхпхпхпхххххххх+ППП
пхпхпхпхпхпхПХХхххххх+ППП
пхпхпхпхпхпххххххх+ПППП
пхпхпхпхпхПХХххххх+ПППП
пхпхпхпхпхххххх+ППППП
пхпхпхпхПХХхххх+ППППП
пхпхпхпххххх+ПППППП
пхпхпхПХХххх+ПППППП
пхпхпхххх+ППППППП
пхпхПХХхх+ППППППП
пхпххх+ПППППППП
пхПХХх+ПППППППП
пхх+ППППППППП
ПХХ+ППППППППП
+ПППППППППП

Остается как-нибудь попроще обосновать, что в наборе из 2N хороших таблеток и N плохих всегда найдутся группы «ПХХ» и «ХХП».
Ясно, что если плохие таблетки расположить равномерно между хорошими, т.е. через 2 на 3-й, то такие группы есть. Также ясно, что если на некотором участке круга расположить плохие таблетки более плотно, то найдется участок, где они будут располагаться более редко, т.к. плотность расположения плохих (и хороших тоже) остается постоянной:
N/(2N + N) = 1/3.
Т.е., если плохие таблетки на каком-то участке расположены, к примеру, так:
...ПХППХППХП...,
то найдется участок, к прмеру, такой:
...ХПХХХПХХП...
Но как-то это всё шероховато. Надо подумать, но почти уверен, что надо применить прицип Дирихле.

На картинке наглядный пример.

не представился 2019-04-05 10:35:05 пишет:

KoKos, я как-то сквозь пальцы пропустил Ivana2000 "Забываем про эту группу", и поэтому вообще не понял к чему Ваше "поскольку по условию плохие таблетки снимать вроде как нельзя". Но если следующие группы "ПХХ" виртуальные, то таки да.

KoKos 2019-04-05 01:00:19 пишет:

не представился, а зачем Вам ПХХ в первых восемнадцати? Подходящее ПХХ на позициях 19-21 - первый берет 20, второй 21, 19 плохая остается лежать на столе, но в уме ее уже как бы нет. Получается ПХПХПХПХПХПХПХПХПХ...ХХХХХХХХХ - и теперь следующее ПХХ уже на позициях 17-22, первый берет 18, второй 22, 17П опять "остается в уме" - ПХПХПХПХПХПХПХПХ......ХХХХХХХХ - и так далее.

Собственно, способ очень красивый, если не считать того, что П не убираются и мешают считать обоим - даже первому, который, хоть и знает и так где они, но теперь должен еще и помнить, какие именно из них уже "типа сняты". 8))

не представился 2019-04-05 00:17:24 пишет:

ivana2000, а если, что-то типа:
"ПХПХПХПХПХПХПХПХПХПХХХХХХХХХХХ"
Где Вы найдете "ПХХ" в первых 18.
KoKos, ну на счет памяти, это я преувеличил. В принципе, в моем алгоритме, плохие тоже выделяются, так как, и "по часовой" и "против часовой", я предлагаю брать первую хорошую.

KoKos 2019-04-04 21:21:28 пишет:

ivana2000, подходит. Но очень легко запутаться - поскольку по условию плохие таблетки снимать вроде как нельзя ("После 20 ходов на столе должны остаться 10 плохих таблеток."), надо будет иметь обоим память на порядок лучше, чем требует не представился для второго...

ivana2000 2019-04-04 20:51:11 пишет:

«Х» – хорошая, «П» – плохая.
Договариваемся о направлении обхода.
Если хороших 20, а плохих 10, то найдется группа «ПХХ». Первый находит эту группу и берет среднюю «Х», второй должен (по начальному сговору) взять третью «Х». Итого: 2 хороших таблетки снято и уже обоим известна плохая – первая таблетка в этой группе. Забываем про эту группу и считаем, что есть
20 – 2 = 18 хороших и
10 – 1 = 9 плохих.
Если хороших 18, а плохих 9, то найдется группа «ПХХ». Первый находит эту группу .... и.т.д., и.т.д., и.т.д., пока не останется только одна группа «ПХХ».
Коряво как-то. Надо еще подумать.

KoKos 2019-04-04 02:06:10 пишет:

Пример 4 тоже не настолько сложен, но интересен демонстрацией разных способ резета второго. На втором ходу второй закончил свою начальную цепочку, но он об этом еще не знает, и если первый ничего не предпримет, то второму грозит плохая таблетка - на третьем ходу первый резетит второго, взяв прижатую таблетку. На пятом ходу второй упирается в резет сам, и первый переводит его на новую цепочку, а сам продолжает выбирать нечеты. На седьмом ходу второй опять заканчивает свою цепочку и опять рискует - первый резетит его восьмым ходом, начав двойку, второй не может продолжать свою тройку ибо первый подпер его дыркой через одну таблетку, - так что второй резетится и опять плетется за первым. На девятом ходу первый снова резетит прижатой таблеткой.

KoKos 2019-04-04 01:46:37 пишет:

Не мудрствуя лукаво, стырю сложные примеры у предыдущего оратора и разберу своим способом. :))) Пример 3: Первый начинает с тройки, а вторым ходом забирает единичку, так что второй, продолжающий выбирать тройку, упирается в состояние "резет" сам и дальше покорно следует за первым, выбирая все пары.

KoKos 2019-04-04 01:22:35 пишет:

Хм... Ну на все-все-все случаи жизни я не проверил, возможно где-то и прохлопал чего, но вроде работает.

Алгоритм такой:
1. Договариваются о направлении обхода, допустим по часовой стрелке.
2. Первый выбирает самую длинную цепочку хороших таблеток и берет первую вдоль обхода из этой цепочки, а второй, соответственно, следующую вдоль обхода.
3. Если есть цепочки хороших таблеток состоящие из нечетного их количества, то первый оставляет второго продолжать выбирать таблетки из начальной цепочки а сам каждым следующим ходом выбирает по одной таблетке из начал всех нечетных цепочек.
4. Второй, будучи предоставлен сам себе, продолжает брать таблетки из начальной цепочки до тех пор, пока
а) либо не упрется сам в положение, при котором по направлению обхода остается всего одна таблетка до "дырки" уже ранее взятой первым (поскольку первый всегда берет начала цепочек, то таблетка прямо перед дыркой гарантированно плохая)
б) либо первый не остановит его специально в случае опасности - для этого первый должен взять таблетку из любой (возможно и этой же) цепочки, "прижатую" таблетку, непосредственно следующую за уже ранее взятой дыркой.
5. В случае "резета" второго (сам ли закончил, или остановлен первым) он опять берет следующую за первым таблетку и опять продолжает выбирать уже новую цепочку, и т.д.

не представился 2019-04-03 13:45:25 пишет:

Кстати, если конечно в предыдущем решении нет изъянов (и кто-то предложит структуру, которую я, как ПЕРВЫЙ, не смогу решить), условие "КАЖДЫЙ видит, какую таблетку взял партнер" не обязательно. Достаточно видеть только ВТОРОМУ (у него ходы, исключением некоторых вариантов заключительных ходов, однозначны). ПЕРВЫЙ же заранее определяет ход ВТОРОГО - зачем ему видеть :)

не представился 2019-04-03 13:29:56 пишет:

Я думаю, что, с учетом существенного различия хороших/плохих (2/1) таблеток, направление "по часовой стрелке" или "против часовой стрелке" визуально определить не трудно.
1. При первом ходе ПЕРВЫЙ обязательно берет за плохой (по часовой стрелке) таблеткой.
2. Если ПЕРВЫЙ при следующем (по отношении к СВОЕМУ предыдущему) ходе берет "против часовой стрелке", то он его делает так, что таблетка перед (против часовой стрелке) той, что он взял - плохая.
3. Если ПЕРВЫЙ при следующем (по отношении к СВОЕМУ предыдущему) ходе берет "по часовой стрелке", то он не должен перескакивать через группу (больше одной) из хороших таблеток, и предыдущая (как и в пункте 1) таблетка должна быть плохой, за исключением, когда при ходе вообще нет перескакивания через таблетки.
4. Если ПЕРВЫЙ при следующем (по отношении к СВОЕМУ предыдущему) ходе берет "по часовой стрелке", то ВТОРОЙ должен взять таблетку следующую (по часовой стрелке) за той, что взял ПЕРВЫЙ.
5. Если ПЕРВЫЙ при следующем (по отношении к СВОЕМУ предыдущему) ходе берет "против часовой стрелке", то ВТОРОЙ должен взять таблетку следующую (по часовой стрелке) за той, что он взял до того (за исключение, когда следующая таблетка уже ранее известна как плохая. Это может возникнуть в самом конце, когда все плохие таблетки уже станут известными).

Для ВТОРОГО необходимо следовать пунктам 4, 5. Естественно ВТОРОЙ должен обладать хорошей памятью, и запоминать все плохие таблетки (с учетом пунктов 1-3).

Общая стратегия ПЕРВОГО заключается (естественно примения движение "против часовой стрелке") в исключении групп хороших таблеток, состоящих из нечетного числа. При этом, по возможности (если позволяет условие корректного определения направления), в первую очередь убирать одиночные таблетки, а при "зачетнивании" группы из трех, пяти и т.д. переходить на другую нечетную группу.

ПЕРВЫЙ должен определить (изначально просчитать как шахматист) свой первый ход. Первым ходом берем, с учетом пункта 1, таблетку из самой большой, если такова имеется, группы хороших таблеток, состоящей из четного количества. Далее ПЕРВЫЙ двигается (если конечно есть нечетные группы) "против часовой стрелки". Если нечетных групп нет, то все просто.

Несколько примеров из структур, на мой взгляд с ярко выраженными особенностями. "0" - плохая таблетка, "1" - хорошая. Круг условно размыкаем в отрезок. Первым ходом является вторая таблетка отрезка.

Пример 1.
011011011011011011011011011011 - все просто: (точка показывает текущий ход ПЕРВОГО; запятая - ВТОРОГО; таблетка после которой побывала точка или запятая считается убранной, но далее показывается условно).
01.1011011011011011011011011011
011,011011011011011011011011011
01101.1011011011011011011011011
011011,011011011011011011011011 и т.д.

Пример 2.
011111111111111111111000000000 - все вообще элементарно.

Пример 3. (на мой взгляд один из самых сложных)
011011011011011011011011011101 -
01.1011011011011011011011011101
011,011011011011011011011011101
01101.1011011011011011011011101
011011,011011011011011011011101
...
01101101101101101101101101.1101
011011011011011011011011011,101
011011011011011011011011011101.
0110110110110110110110110111,01 - здесь игнорируется правило пункта 5.

Пример 4.(на мой взгляд один из самых сложных).
011101110111011101110111011000 -
01.1101110111011101110111011000
011,101110111011101110111011000
011101110111011101110111011.000
0111,01110111011101110111011000
011101.110111011101110111011000
0111011,10111011101110111011000
01110111011101110111011101.1000
01110111,0111011101110111011000
0111011101.11011101110111011000
01110111011,1011101110111011000
01110111011101.1101110111011000
011101110111011,101110111011000
011101110111.011101110111011000
0111011101110111,01110111011000
011101110111011101.110111011000
0111011101110111011,10111011000
0111011101110111011101.11011000
01110111011101110111011,1011000
01110111011101110111.0111011000
011101110111011101110111,011000

Пример 5.
011111101010000001111111011111 -
01.1111101010000001111111011111
011,111101010000001111111011111
011111101010000001111111011111.
0111,11101010000001111111011111
011111101010000001111111.011111
01111,1101010000001111111011111
01111110101.0000001111111011111
011111,101010000001111111011111
011111101.010000001111111011111
0111111,01010000001111111011111
011111101010000001.111111011111
0111111010100000011,11111011111
01111110101000000111.1111011111
011111101010000001111,111011111
0111111010100000011111.11011111
01111110101000000111111,1011111
01111110101000000111111101.1111
011111101010000001111111011,111
0111111010100000011111110111.11
01111110101000000111111101111,1

P.S. Может выше изложенное сильно сложно, и можно оптимизировать, но на вскидку (намного дольше описывал) у меня видение такое.

Добавьте комментарий:

Обсуждаем

Задача Разрезанный треугольник:
http://lprobs.ru/img/yes.gif : [скрыто]
Гостевая книга:
не представился : Это было в 1913 году. Одиннадцатилетняя девочка, пансионерка Московской Ржевской гимназии очень прос...
Задача Гора.:
Xuzke : [скрыто]
Гостевая книга:
не представился : В школе все казалось правильным. Из математики следует физика, из физики следует химия, из химии сле...
R-2 : Ты решил: Ну, и наконец, то решение, которое тут видимо предполагается в идеале, я не буду говори...
Так, по старой памяти заглянул :) : R-2, условие неплохо бы конкретизировать. ;)) А то так вариантов может быть масса, хотя все обладают...
Задача 4 хода:
колд : [скрыто]
Задача Кот и мышка:
Дмитрий : [скрыто]
Задача Черная Жемчужина:
mskfirst : [скрыто]
Задача Квадратный торт:
не представился : [скрыто]
Задача Задача с ведрами: 9 и 4 = 6.:
ИносОйЧанбин : [скрыто]
Дкгк7 : [скрыто]
Задача Геометрическая 3:
не представился : [скрыто]
Алексей : [скрыто]
Гостевая книга:
R-2 : Дано: листочек бумаги и ручка. На листочке написаны три нуля. О О О Задача: «как из трёх нулей...

Реклама

© 2009-201x Логические задачи

Задачи на логику и сообразительность

Поиск на сайте

Задачи

Данетки

Справочная

Реклама

задача: 30 одинаковых таблеток

Ответ

Решение задачи

Ваши ответы на задачу

Обсуждаем

Реклама