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

У вас также есть старомодная шкала баланса.

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

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

Нечетный мяч незаметен простым прикосновением к нему. Весы - единственный способ сравнить мячи. Нет никакой хитрости в масштабе. Невозможно манипулировать им, чтобы получить более одного прямого результата для каждого измерения. Загадка происходит на Земле, в нашей физической вселенной.

Фон

Я работаю в области разработки программного обеспечения более двадцати лет. За это время я много раз брал интервью и давал интервью. По моему опыту, общепринятой практикой является попросить собеседника попытаться решить логическую задачу. Интервьюируемого обычно просят подумать вслух, пока он пытается решить головоломку.

Много лет назад одна из таких логических головоломок, «Задача о весе 12 мячей», была предложена моей команде коллегой. Задача интересна тем, что требует от решателя того же, что инженеры-программисты делают ежедневно: создания умеренно сложного алгоритма с учетом различных пограничных случаев.

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

Итак, в тот вечер я пошел домой и исследовал головоломку. Я был разочарован, снова найдя ряд источников, которые просто давали ответ, не изучая его глубже. Но я нашел один веб-сайт, на котором упоминалось, что полезно отслеживать отдельные состояния каждого мяча (подробнее об этом ниже). Этот намек показал, что головоломка была еще более уместной, потому что инженеры-программисты постоянно имеют дело с управлением состоянием в своих алгоритмах. В конце концов, я смог удовлетворить свое любопытство в отношении того, как можно подойти к задаче о весе 12 мячей.

Я не думал об этом снова в течение многих лет. А вчера вечером представилась возможность поделиться с любителем головоломок решением задачи «12 мячей». Однако моя проблема на этот раз была обратной моей первоначальной проблеме: я забыл конкретное решение, но я помнил общий подход.

Итак, вместе мы сели и решили решить головоломку. В процессе я пришел к лучшему пониманию того, как подойти к этой головоломке. Моя цель — поделиться этим подходом с вами.

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

Кроме того, прежде чем я углублюсь в головоломку, я чувствую необходимость поделиться тем, что я вполне уверен, что логические головоломки — это неэффективное использование драгоценного времени интервью. Соответственно, я бы не советовал вам использовать эту головоломку на собеседовании.

С чего начать

Есть смысл начать с самого начала. Перед вами свежие весы, а рядом с ними двенадцать шариков. Обычно требуется несколько минут на обсуждение различных способов составления первого измерения.

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

Даже если решатель не обнаружит, что в первом измерении нужно использовать восемь шаров (по четыре в каждой чашке), позже мы придем к тому же выводу.

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

Таким образом, если мы сравним группу 1 с группой 2, у нас будет три возможных результата: группа 1 тяжелее группы 2 или группа 1 легче группы 2 или группа 1 такая же, как группа 2. Для первых двух результатов мы знаем, что нечетный мяч должен быть в группе 1 или группе 2, но не может быть в группе 3. В случае Группа 1 такая же, как и Группа 2, мы знаем, что нечетный шар находится в Группе 3.

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

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

Ешьте пиццу, сначала корочку

Поняв, что времени (или, может быть, терпения) уже не хватает, возникает вопрос: «С чего еще я могу начать, кроме как с начала проблемы?»

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

Этикетка, этикетка на мяче, кто из них самый странный?

Как я упоминал во введении, здесь есть еще одно важное понимание. То есть, если мы пометили шарики цифрами, то есть и другие метки, которые мы можем создать. В частности, мы можем пометить каждый мяч его возможными состояниями: Возможно Тяжелый, Возможно Легкий и Возможно Нормальный. Для краткости я буду использовать первую букву прилагательного каждого штата. H = возможно тяжелый, L = возможно легкий и N = возможно нормальный.

Итак, перед нашим первым измерением каждый мяч имел метку «HLN», потому что каждый мяч мог быть тяжелым, легким или нормальным. Больше мы пока ничего не знаем.

В конце концов, после третьего измерения одиннадцать шариков будут иметь только метку «N», а один шарик будет иметь метку «H» или «L».

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

Повторное использование, сокращение, переработка

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

Объединяем

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

Важно помнить, что мы работаем в обратном направлении, чтобы научиться решать головоломку в прямом направлении.

Итак, давайте начнем с самого простого вопроса, который кажется полезным.

1v1

Для двух мячей, где мы знаем, что один из них нечетный, сколько измерений нам потребуется, чтобы определить, какой из них является нечетным и является ли он тяжелым или легким?

Первая мысль, которая приходит на ум, — просто измерить два шара.

В этом эксперименте первый шар поднимается вверх, а второй падает вниз.

В приведенной выше модели либо первый шар легче обычного, либо второй шар тяжелее обычного. Итак, какие ярлыки мы можем снять с этих двух шаров? Мы можем удалить метку «H» с шара номер один, потому что он никак не может быть тяжелее обычного. Либо он легче обычного, либо он нормальный, а шар номер два тяжелее обычного. Мы также можем удалить метку «L» со второго шара, потому что невозможно, чтобы он был легче обычного.

Нам удалось снять по одной этикетке с каждого шарика в обеих чашках. Не слишком потертый! Однако мы до сих пор не знаем, какой из этих шаров лишний. Как мы могли это определить? Ну, очевидно, если мы взвесим те же самые два шара, мы получим тот же результат. Так что единственное, что можно сделать, это поменять местами один из шаров на другой, который, как мы уже знаем, является нормальным. Давайте поменяем шарик два на шар двенадцать.

Возможны два результата.

Если первый шар поднимается вверх, то это должно быть нечетный шар и он легче обычного. Двенадцатый шар не может быть тяжелее первого.

Если шар номер один измеряется так же, как шар двенадцать, то единственное возможное объяснение состоит в том, что оба шара номер один и двенадцать нормальны. Поэтому мы удаляем метку «L» с первого шара. Затем методом исключения второй шар должен быть тяжелее обычного, потому что это единственный оставшийся шар, у которого есть что-то кроме метки «N».

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

Итак, ответ на наш вопрос 1 на 1: два. То есть для двух шаров, с которых ранее не были удалены этикетки, требуется два измерения, чтобы определить, какой из них является лишним.

Но каковы шансы, что мы измерим ровно два шара, с которых не были удалены этикетки при предыдущем измерении? Не очень вероятно. На самом деле, если вы хорошенько все обдумаете, то увидите, что если у двух измеряемых вами шаров по две метки вместо всех трех, вы сможете определить, какой из них является лишним в одном измерении. Это важно: меньшее количество этикеток на шар означает меньшее количество измерений.

2v2

Давайте добавим еще два шара и посмотрим, что мы можем сделать.

Имея четыре мяча, из которых мы знаем, что один из них нечетный, сколько измерений нам потребуется, чтобы определить, какой из них является нечетным и является ли он тяжелым или легким?

Модель выше показывает один возможный результат и соответствующие метки, снятые с шаров.

Ладно, с каждого шарика сняли по одной этикетке — это хорошо! Теперь давайте попробуем поменять местами по одному шарику из каждой тарелки. Теперь мы будем измерять шарик «HN» и шарик «LN» в каждой чашке. Что привлекательно в этой конфигурации, так это то, что независимо от того, в каком направлении расположены кончики шкалы, мы гарантированно уменьшаем два шарика только до меток «N».

Допустим, первый и третий шары поднимаются вверх, а второй и четвертый шары падают вниз. Это означает, что первый шар не может иметь маркировку «H», а четвертый шар не может иметь маркировку «L».

Теперь мы можем отложить два шарика «N» и увидеть, что эта задача теперь точно такая же, как и второе измерение из 1 на 1. Следовательно, мы можем решить отсюда, используя еще одно измерение.

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

Итак, ответ на наш вопрос 2 на 2: три. То есть для четырех шаров со всеми тремя метками требуется три измерения, чтобы определить, какой из них является лишним.

Однако, как и в случае 1 на 1, если в начале у нас есть четыре шара с двумя метками на каждом, мы можем решить задачу всего за два измерения.

3v3

Мы приближаемся! Давайте теперь рассмотрим измерение шести шаров.

Учитывая шесть шаров, где мы знаем, что один из шаров является нечетным, сколько измерений нам потребуется, чтобы определить, какой из них является нечетным и является ли он тяжелым или легким?

Допустим, первый, второй и третий шары поднимаются вверх. Таким образом, эти шары обозначаются как «LN», а шары четыре, пять и шесть — как «HN».

Ладно, пока все хорошо. Давайте попробуем поменять местами шарик с каждой тарелки, как мы это делали в 2 на 2, так что независимо от результата мы обязательно снимем этикетки с каждой стороны.

После удаления меток мы можем отложить два шара «N», что оставит нам четыре шара, каждый с двумя метками.

Мы знаем из 2v2, что отсюда можно решить с двумя дополнительными измерениями. Но подождите — это четыре измерения для игры 3 на 3! Но опять же, мы можем предположить, что мы не будем начинать с того, что каждый шар будет иметь все три метки. А это значит, что мы можем решить 3 на 3 за три хода. Но этого еще недостаточно. При решении головоломки вперед мы начнем измерение как минимум 4 на 4. И мы уже заявили все три измерения для 3 на 3.

Есть ли способ лучше? Давайте попробуем применить принцип повторного использования.

Немного перемотаем часы. И на этот раз, после того, как мы поменяем шар из каждой тарелки, давайте также поменяем один шар из одной из тарелок на известный шар «N». Мы заменим шар шесть и заменим его шаром двенадцать.

Если шары один, два и четыре поднимутся вверх, то у нас останется три шара «N» вместо двух, которые были у нас с первой попытки.

Можем ли мы собрать два шара «LN» и один шар «HN» за один ход? Да, мы можем, просто измерив два шара с одинаковыми метками. В данном случае мяч один и мяч два. Если первый шар поднимается вверх, то первый шар является нечетным и легче обычного. Если шар номер два поднимается вверх, то это нечетный шар и он легче обычного. Если первый и второй шары одинаковые, то пятый шар нечетный и тяжелее обычного.

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

Вау, мы сделали это! Мы решили 3 на 3 всего за два измерения — при условии, что мы можем начать с шаров, у каждого из которых есть только две метки. Это контринтуитивный результат. Заменив один мяч на обычный, мы оптимизировали производительность игры 3 на 3.

Вы можете вернуться и попробовать разные результаты для каждого измерения, но общее количество никогда не должно быть больше двух.

4v4

Посмотрим, сможем ли мы решить 4 на 4 за три хода.

В приведенной выше модели шары с первого по четвертый подняты вверх. Есть еще один результат, который нам нужно будет рассмотреть позже (шары с первого по четвертый совпадают с шарами с пятого по восьмой). А пока, что нам делать? Здесь в основном два варианта. Мы можем поменять местами несколько шаров и снова измерить восемь шаров. Но мы знаем, что 2v2 и 3v3 требуют по два измерения для шаров с двумя метками. Всего нам разрешено только три хода. Таким образом, следующее измерение должно быть либо 2 на 2, либо 3 на 3.

Мы отложим мячи четыре и восемь. Теперь это именно та проблема, которую мы решили в 3х3. Мы можем решить ее в два хода. Но что, если мячи с первого по третий имеют такие же размеры, как мячи с пятого по седьмой? Тогда нечетный шар равен четырем или восьми. Мы можем выяснить, какой из них за один ход, используя ту же технику, что и в 1 на 1.

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

2 на 2 часть двое

Ранее мы видели, что 3 на 3 может превзойти 2 на 2. Давайте попробуем решить 2 на 2, используя 3 на 3.

Мы кладем шарики с девяти по одиннадцать в одну тарелку и три обычных шара в другую тарелку.

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

Итак, допустим, что шары с девятого по одиннадцатый падают вниз.

Из этого результата мы знаем, что один из шаров с девятого по двенадцатый должен быть нечетным, и поэтому двенадцатый шар является нормальным. Теперь нам просто нужно измерить шар девять против шара десять, и вы можете решить остальное.

Но что, если шары с 9 по 11 такие же, как шары с 1 по 3? Просто измерьте шар двенадцать против обычного шара, и вы снова сможете вычислить остальные.

В любом из этих случаев мы можем решить четыре шара со всеми тремя метками в двух измерениях. Мы только что оптимизировали пограничный случай 2 на 2! 3 на 3 это что-то волшебное.

Заключение

Нам не нужно рассматривать 5 на 5, потому что мы можем решить всю головоломку, продвигаясь вперед в трех измерениях, начиная с 4 на 4.

Я надеюсь, что это объяснение будет кому-то полезно. Было весело записывать это.

Хорошего дня!