Головоломка: найдите минимальное количество гирь

Question

Я сталкивался с этим вопросом: скажем, учитывая две веса 1 и 3, вы можете весить 1,2 (на 3-1), 3,4 (на 3 + 1) (используя обе стороны баланса). Теперь найдите минимальное количество весов, чтобы вы могли измерить от 1 до 1000.

Итак, ответ был 1,3,9,27 ...

Я хочу знать, как вы пришли к такому решению, означает полномочия 3. Что такое мыслительный процесс?

Источник: http://classic -puzzles.blogspot.com / search / label / Google% 20Interview% 20Puzzles

Решение: http://classic -puzzles.blogspot.com / 2006/12 / solution-to-shopkeeper-problem.html

Answer 1

Вот как я решил проблему. Скажем, у вас есть веса a_1, a_2, ..., a_r.

Теперь вы можете взвесить вес, если у вас есть

a_i1 + a_i2 + ... + a_ik = x + a_j1 + a_j2 + ... + a_jl

т.е. x = Sum e_i * a_i

, где e_i равен -1, 0 или 1.

т.е.. нам нужно записать каждое число в виде линейной комбинации a_i с коэффициентами 1,0 или -1.

Теперь мы знаем, что мы можем написать любое число в базе 3 как комбинацию степеней 3 с коэффициентами (цифрами) 0,1,2.

Аналогичный факт заключается в том, что мы также можем использовать цифры 1, 0 и -1, когда пишем число в базе 3!

Тот факт, что нам нужно получить все возможные числа, приводит к тому, что вы, возможно, сможете использовать степени 3.

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

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

И еще одна проблема:

Предположим, я сказал, что у вас есть две копии каждого веса и общего баланса, и вам нужно было взвешивать все веса от 1 до 61. Какие веса вы бы выбрали?

Answer 2

Рассмотрим проблему на базовом уровне:

Если вы хотите найти минимальный вес для 20 кг,

Первоначально: 20 = 1 + 1 + 1 + 1 + 1 + 1 .... (20 раз). Используя двоичный файл, вы можете разбить его на половину, используя только нечетные веса.

  => 1, 2, 4, 6, 8, 10...20 (for all odd weights even no.s can be "added" by 1)
      ... 2+1, 4+1, 6+1...18+1.

Теперь, если также учитывается «вычитание», т. Е. Используются оба сковороды, тогда мы можем взять кратные 3.

1     3        6        9       12        15        18        21        24        27

   2     4  5     7  8    10  11    13 14     16 17     19 20     22 23     25 26

       _________________  _________________  __________________  ___________________

Мы видим, что все веса могут быть получены, таким образом, добавляя и вычитая 1 к кратному 3

IMP: 1 был базовой единицей выше

Далее мы можем сделать 3 основной единицей сложения и вычитания, так как она может вывести все остальные числа. Следовательно, рассмотрим множества, 3-6-9, 9-12-15, 16-17-18 и т. Д., И средние слагаемые можно исключить как.

Таким образом, мы имеем,

1     3                9                    15                   21                 27

   2     4  5  6  7  8    10  11  12  13 14     16 17  18  19 20     22 23 24 25 26

                          _________________    __________________  __________________

Теперь 9 является нашей основной единицей, поскольку мы можем получить доступ к любому номеру от 1 до 9 напрямую. Если мы добавим или вычтем, мы получим разрыв 18. Таким образом, мы удалили средние термины:

1     3                9                                                           27

   2     4  5  6  7  8   10  11  12  13 14  15  16 17  18  19 20  21 22 23 24 25 26

                          _________________________________________________________

Теперь можно вывести каждое число от 1 до 27. Следовательно, 27 становится нашей основной единицей, и следующий пробел, который может быть доступен, будет включать сложение и вычитание 27, что дает 54.

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

Следовательно доказано.

Answer 3

Теорема: вам понадобятся веса от 3 ^ 0 до 3 ^ N, чтобы покрыть значения от 1 до S (N) = сумма (3 ^ i) для i = 0 до N.

Доказательство:

1. Вы дали базовый случай, где N = 1.
2. Теперь предположим, что это верно для N = 3 ^ M - S (M-1). То есть, если 3 ^ M <= 1 + 2 * S (M-1) = 1 + сумма (2 * 3 ^ i) для i = 0 до M-1. Это кажется мне ясным в данный момент, но у меня было несколько коктейлей, и доказательство было не совсем тем, о чем вы просили, так что я оставлю этот последний шаг в качестве упражнения для читателя. </li>
3. По индукции, QED.

Answer 4

Предположим, у вас есть набор весов, с помощью которого вы можете взвесить любое число до n. Теперь вы хотите расширить свой набор весов, чтобы весить больше чисел, что означает, что вы хотите весить n + 1, n + 2 и так далее. Добавление весов n + 1, n + 2, ...., 2n было бы излишним. Следующим весом в серии должно быть ((сумма всех предыдущих весов) * 2) + 1)

Я думаю, вы просто начнете с базового варианта 1 и продолжите свой путь. Чтобы попасть в число 2, вы можете выбрать {2, 3, 4 ...}. 4 - 1 не может достичь, 2 является избыточным. После еще одного номера появляется шаблон.