1 сент. 2008 г.

День знаний

Поздравляю всех с началом учебного года!

Раз такое дело, то давайте и мы узнаем продолжение решения задачи о взвешиваниях.

Мы остановились на том, что меньше четырёх гирек заведомо мало, а шести хватает. Давайте попробуем найти способ представить любой вес от 1 до 40 четырьмя гирьками.

Пусть одна гирька весит x килограммов. Тогда она одна поможет нам взвесить x, 0 или -x килограммов. В самом деле, гирьку ведь можно класть на ту же чашу весов, что и груз!

Можно считать, что положение наших гирек описывается троичными битами (битами с тремя состояниями). Тогда сразу возникает желание сделать и веса гирек степенями тройки (1, 3, 9, 27) и подумать. И оказывается, что думать-то после этого уже не надо :)

Легко убедится, что этих гирек хватит, чтобы выразить любой целый вес от 1 до 40 :)

Скоро я вернусь с кучей впечатлений, буду делиться :)
До встречи! И хорошей недели!

5 комментариев:

  1. Анонимный08.09.2008, 08:53

    Здравствуйте, а не могли бы вы по подробней объяснить как "x, 0 или -x килограммов" увязывается со степенями чила 3. Спасибо.

    ОтветитьУдалить
  2. krilya, спасибо за вопрос. Я подготовлю понятную иллюстрацию, потому что словами коротко объяснить не получается. В одной из следующих заметок мы обсудим детали решения.

    ОтветитьУдалить
  3. Лучше поздно, чем никогда - обещанное объяснение (я не смог придумать хорошую иллюстрацию, поэтому всё текстом)

    ОтветитьУдалить
  4. Анонимный08.11.2009, 20:24

    К решению можно прийти из более прозрачных (как по мне) размышлений.
    Естественно нужно взять гирю в 1кг. Далее будем рассматривать вес по нарастанию и, если не хватает нашего набора, будем получать его вычитанием наших гирь из новой гири.
    На деле:
    набор {1}
    2=3-1 (набор {1,3}, из него имеем 1-4)
    5=9-4 ({1,3,9}, имеем 1-13)
    14=27-13 ({1,3,9,27}, имеем 1-40)

    ОтветитьУдалить
  5. Уважаемый аноним, спасибо за короткое изложение подхода к задаче!

    ОтветитьУдалить