Можно ли заказать набор из семи таких гирек, чтобы ими можно было взвесить любой слиток золота весом от 1 грамма до 1 килограмма? Слиток золота весит целое число грамм, гирьки можно класть на обе чаши весов.
Эту задачу мой младший брат решал на собеседовании в Abbyy.
Решение
Нужны гирьки весом 1г, 3г, 9г, и далее по степеням тройки до 729г. Этим набором гарантированно можно будет взвесить любой слиток до 1 кг.
Доказать этот факт можно несколькими способами. Чтобы вспомнить школьную математику, я приведу здесь доказательство методом математической индукции.
Докажем, что гирьками весом от 1, 3, 9,...,3^n можно взвесить любой слиток весом от 1 до (3^(n+1)-1)/2 включительно.
Для n=1 утверждение очевидно. Имея гирьки 1г и 3г, можно взвесить 1, 2, 3 и 4 грамма (для 2г гирьки кладём на разные чаши, для 4г - на одну чашу).
Пусть у нас есть гирьки весом 1,3,...,3^(n-1), которыми мы можем взвесить любой слиток весом до (3^n-1)/2 включительно. В нашем распоряжении появляется новая гирька весом 3^n. Покажем, что с её помощью можно взвесить все слитки весом до (3^(n+1)-1)/2 включительно.
Слитки весом до (3^n-1)/2 мы уже умеем взвешивать по предположению индукции.
Если слиток весит X грамм, больше (3^n-1)/2, но меньше 3^n, то на правую чашу мы помещаем гирьку 3^n, а оставшиеся гирьки размещаем так, как если бы мы взвешивали на правой чаше слиток весом (3^n-X). Если X > (3^n-1)/2, то 3^n-X < 3^n - (3^n-1)/2 = (3^n-1)/2+1, а т.к. X - целое, то 3^n-X<=(3^n-1)/2. Таким образом, по предположение индукции, мы всегда сможем выложить нужный остаток на левой чаше.
Если слиток весит ровно 3^n, то его взвешивание тривиально.
Если слиток весит Y грамм, больше 3^n, но не больше (3^(n+1)-1)/2, то на правую чашу мы помещаем гирьку 3^n, а оставшиеся размещаем так, как если бы мы взвешивали на левой чаше слиток весом (Y-3^n). Т.к. Y <= (3^(n+1)-1)/2, то Y-3^n <= (3^(n+1)-1)/2 - 3^n = (3^n-1)/2. Следовательно, по предположению индукции, мы всегда сможем выложить нужный остаток на правой чаше.
Утверждение доказано.
Таким образом, имея гирьки весом 1г, 3г, 9г, 27г, 81г, 243г и 729г, мы сможем взвешивать слитки весом до 1093г включительно.
Эту задачу мой младший брат решал на собеседовании в Abbyy.
Решение
Нужны гирьки весом 1г, 3г, 9г, и далее по степеням тройки до 729г. Этим набором гарантированно можно будет взвесить любой слиток до 1 кг.
Доказать этот факт можно несколькими способами. Чтобы вспомнить школьную математику, я приведу здесь доказательство методом математической индукции.
Докажем, что гирьками весом от 1, 3, 9,...,3^n можно взвесить любой слиток весом от 1 до (3^(n+1)-1)/2 включительно.
Для n=1 утверждение очевидно. Имея гирьки 1г и 3г, можно взвесить 1, 2, 3 и 4 грамма (для 2г гирьки кладём на разные чаши, для 4г - на одну чашу).
Пусть у нас есть гирьки весом 1,3,...,3^(n-1), которыми мы можем взвесить любой слиток весом до (3^n-1)/2 включительно. В нашем распоряжении появляется новая гирька весом 3^n. Покажем, что с её помощью можно взвесить все слитки весом до (3^(n+1)-1)/2 включительно.
Слитки весом до (3^n-1)/2 мы уже умеем взвешивать по предположению индукции.
Если слиток весит X грамм, больше (3^n-1)/2, но меньше 3^n, то на правую чашу мы помещаем гирьку 3^n, а оставшиеся гирьки размещаем так, как если бы мы взвешивали на правой чаше слиток весом (3^n-X). Если X > (3^n-1)/2, то 3^n-X < 3^n - (3^n-1)/2 = (3^n-1)/2+1, а т.к. X - целое, то 3^n-X<=(3^n-1)/2. Таким образом, по предположение индукции, мы всегда сможем выложить нужный остаток на левой чаше.
Если слиток весит ровно 3^n, то его взвешивание тривиально.
Если слиток весит Y грамм, больше 3^n, но не больше (3^(n+1)-1)/2, то на правую чашу мы помещаем гирьку 3^n, а оставшиеся размещаем так, как если бы мы взвешивали на левой чаше слиток весом (Y-3^n). Т.к. Y <= (3^(n+1)-1)/2, то Y-3^n <= (3^(n+1)-1)/2 - 3^n = (3^n-1)/2. Следовательно, по предположению индукции, мы всегда сможем выложить нужный остаток на правой чаше.
Утверждение доказано.
Таким образом, имея гирьки весом 1г, 3г, 9г, 27г, 81г, 243г и 729г, мы сможем взвешивать слитки весом до 1093г включительно.
Комментариев нет:
Отправить комментарий