Проблема

«На острове 12 человек. 11 весят ровно столько же, но один из них немного легче или тяжелее. Вы должны выяснить, какой…. На острове нет весов, но есть качели. Интересный улов? Вы можете использовать его только 3 раза».

Условия статьи:

  1. Вариант — островитянин, который весит нестандартный вес. Неизвестно, весит ли этот островитянин тяжелее или легче остальных.

2. «n-/n+» — островитяне пронумеровали букву «n» как вариант, «-» означает более легкий, а «+» означает более тяжелый.)

Ключевая информация

Все 12 островитян могут быть тяжелее или легче, поэтому существует 24 возможности варианта. Качели могут дать 3 результата: L ‹ R, L › R или L = R. В идеале результат каждого взвешивания должен делить оставшиеся возможности равномерно распределяются между тремя возможными исходами (›, ‹, =), чтобы максимизировать эффективность.

Решение

Группа А: Айлендерс 1–4

Группа B: «Айлендерс» 5–8

Группа C: Айлендерс 9–12

Первое взвешивание: 1–4 против 5–8. (AAAA, BBBB)

Из первоначальных 24 вариантов, взвешивание двух групп по 4 человека друг против друга эффективно разделяет результаты на четные 8/8/8 вариантов для каждого результата:

Если A ‹ B, то возможности: 1-, 2-, 3-, 4-, 5+, 6+, 7+, 8+

Если группа A легче группы B, то в группе A есть либо более легкий вариант, либо в группе B более тяжелый вариант (см. следующий раздел).

Если A › B, то возможности: 1+, 2+, 3+, 4+, 5-, 6-, 7-, 8-

Обратное верно; если группа A тяжелее группы B, то в группе B есть более легкий вариант, а в группе A — более тяжелый вариант (см. следующий раздел).

Если A = B, то возможности: 9-, 10-, 11-, 12-, 9+, 10+, 11+, 12+

Если группы A и B весят одинаковый вес, то вариант находится в группе C (островитяне 9–12), но имеет неизвестный вес (см. раздел после следующего).

Что, если группа А и группа Б неравны? ("")

(Комплексное) 2-е взвешивание: 1, 2, 5 против 3, 6, 9 (AAB против ABC)

  1. На тех же сторонах, что и их соответствующие позиции при первом взвешивании, находятся островитяне 1, 2 и 6 (AAB против ABC).
  2. На противоположных сторонах от своих позиций после первого взвешивания находятся «Айлендерс» 5 и 3 (AAB против ABC).
  3. Из первого взвешивания исключены островитяне под номерами 4, 7 и 8. (A, B и B)
  4. Во втором взвешивании впервые представлен островитянин 9 (AAB против ABC), который должен взвесить стандартное количество.

Зачем использовать эту сложную комбинацию островитян для второго взвешивания?

Второе взвешивание в идеале делит оставшиеся 8 возможностей на 3/3/2 или аналогичный разброс.

Если A ‹ B, оставшиеся возможности: 1-, 2-, 3-, 4-, 5+, 6+, 7+, 8+.

При (комплексном) втором взвешивании 1, 2, 5 против 3, 6, 9 суженные варианты вариантов:

‹: 1-, 2-, 6+ (Если результат останется тем же, то вариантом могут быть только островитяне, которые были на той же стороне, что и при первом взвешивании. Их потенциальный вес как варианта определяется по первому взвешиванию; Островитяне 1 или 2 должны быть легче, или 6 должны быть тяжелее.)

›: 3-, 5+ (Если результат меняет неравенства, то вариантом могут быть только островитяне, которые поменялись сторонами при первом взвешивании. Их потенциальный вес в качестве варианта определяется по первому взвешиванию; Islander 3 должен быть легче, или Islander 5 должен быть тяжелее.

=: 4-, 7+, 8+ (Если результат становится равным, то вариантом могут быть только островитяне, исключенные из предыдущего взвешивания. Их потенциальные веса как варианта даны из сначала взвесьте; либо «Айлендерс 4» должен быть легче, либо «Айлендерс» 7 или 8 должны быть тяжелее.)

Хотя применима та же логика, я быстро отмечу возможности в случае, когда A > B: 1+, 2+, 3+, 4+, 5-, 6-, 7-, 8-. Суженные варианты (Примечание: они упорядочены в зависимости от того, насколько схожи результаты первого и второго взвешивания, поэтому порядок может немного отличаться от предыдущего списка).

>: 1+, 2+, 6-

<: 3+, 5-

=: 4+, 7-, 8-

Что, если группа А и группа Б весят одинаковое количество?

Это второе взвешивание идеально делит 8 возможностей на 3/3/2 или аналогичный разброс. В этом случае все островитяне в группах A и B должны иметь стандартный вес, что означает, что вариант находится в группе C (островитяне 9–12). Однако мы не знаем, тяжелее или легче этот вариант. 8 возможностей: 9-, 10-, 11-, 12-, 9+, 10+, 11+, 12+.

(Простое) 2-е взвешивание: 9, 10 против 11, 1 (CC против CA)

  1. Островитянин 12 намеренно опущен, чтобы были случаи, когда равенство может быть возможным. На месте можно использовать любой островитянин стандартного веса.

(Простое) Второе взвешивание сужает возможности:

<: 9-, 10-, 11+

>: 9+, 10+, 11-

=: 12-, 12+

Окончательное взвешивание

На этом этапе должно быть не более 3 вариантов вариантов. Самый простой способ присвоить каждому варианту уникальный результат — объединить более легкий и тяжелый вариант вместе с двумя островитянами со стандартным весом.

Например, если первый и второй результаты взвешивания равны «=» и «›» соответственно, то вариант будет 9+, 10+ или 11- (на основе предыдущего списка). Мы можем взвесить 9 и 11 (+ и -) против 1 и 2 (стандартный вес).

Если L ‹ R, 11 — более легкий вариант.

Если L > R, то 9 — более тяжелый вариант.

Если L = R, пропущенный путешественник является вариантом, что в данном случае означает, что 10 тяжелее.

(В уникальном случае «=» и «=» в первых двух взвешиваниях, взвесьте островитянина 12 против любого другого островитянина, чтобы определить, легче или тяжелее островитянин 12.)

Дополнительные комментарии

Как выбрать, кого взвешивать

Первое взвешивание: 1–4 против 5–8 (AAAA против BBBB)

Взвешивание 6 против 6 — самая распространенная ошибка в этой головоломке. Интуитивно, лучшим подходом будет каждый раз уменьшать результаты вдвое, верно? B99 на самом деле демонстрирует эту общую линию мышления, когда Эми Сантьяго предлагает это в своем решении, но ее тут же останавливает ее босс, говоря ей, что она неправа. Это не работает, поскольку не позволяет иметь место равенству и не предоставляет никакой информации о том, что это за вариант.

Некоторые могут возразить, что взвешивание 6 против 6 действительно работает; в решениях, с которыми я сталкивался от других, я обнаружил, что распространенной ошибкой тех, кто утверждает, что это работает, было предположение, что вес варианта указан. Свободная интерпретация формулировки головоломки может означать, что вам нужно найти решение, которое работает как в случае более тяжелого варианта, так и в случае более легкого варианта, что будет значительно проще. Но настоящая проблема в том, что неясно, тяжелее или легче этот вариант, поэтому вы должны определить, какой островитянин является вариантом, а также тяжелее или легче они.

К счастью, количество возможностей (12 * 2 = 24) можно разделить на количество исходов (3), что означает, что взвешивание группами по 4 человека — лучший подход для первого взвешивания.

(Комплексное) Второе взвешивание: 1, 2, 5 против 3, 6, 9 (AAB против ABC)

Вероятно, существует несколько стратегий, которые подходят для этого веса, поскольку это довольно сложно и существует много разных возможностей. Однако я считаю, что большинство из них представляют собой аналогичные варианты решения, которое я нашел, в котором два островитянина удаляются (A и B с обеих сторон), двое меняются местами (B слева и A справа) и один заменяется (B справа заменено на C). Я пришел к этому решению, отметив и применив некоторые закономерности:

  1. Удаление островитян с обеих сторон

Удаление островитян с обеих сторон означает, что неравенство может измениться на равенство, если любой из удаленных островитян является вариантом.

2. Обмен островитян на противоположные стороны.

Перестановка островитян на противоположные стороны означает, что неравенство может измениться на противоположное неравенство, если любой из замененных островитян является вариантом.

3. Замена Айлендера на стандартного

Замена островитянина островитянином стандартного веса может изменить неравенство на равенство, аналогично удалению островитян. Однако, чтобы результат качелей был значимым, количество островитян на каждой стороне всегда должно быть равным, поэтому мы можем заменить его островитянином, вес которого уже известен.

Подход к кодированию

Я собираюсь вскоре опубликовать реализацию на Python и рассказать, как я применил эту логику. Как только я закончу это, я приложу сюда ссылку, так что следите за ней!