ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98499
Темы:    [ Взвешивания ]
[ Двоичная система счисления ]
[ Деление с остатком ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

Автор: Калинин А.

На правой чаше чашечных весов лежит груз массой 11111 г. Весовщик последовательно раскладывает по чашам гири, первая из которых имеет массу 1 г, а каждая последующая вдвое тяжелее предыдущей. В какой-то момент весы оказались в равновесии. На какую чашу поставлена гиря 16 г?


Решение 1

  Остаток от деления числа 11111 на 64 равен 39. Сумма весов всех выложенных гирь при делении на 64 даёт остаток  1 + 2 + ... + 32 = 63  (очевидно, первые 6 гирь были выложены). Поэтому остаток от деления на 64 общей массы, лежащей на весах, равен 38. Следовательно, остаток от деления на 32 массы, лежащей на каждой чаше, равен 19. Сумма  1 + 2 + … + 16  меньше 32, поэтому общая масса тех из первых пяти гирь, которые лежат на левой чаше равна 19. Очевидно, это гири массой 1 г, 2 г и 16 г.


Решение 2

  Пусть равновесие наступило, когда на весы положена всего  n + 1  гиря – некоторые на левую, некоторые на правую чашу весов:
11111 + 2b1 + 2b2 + ... + 2bk  = 2a1 + 2a2 + ... + 2ap,  причём  k + p = n + 1  и среди чисел a1, a2, ... , ap, b1, b2, ... , bk встречаются по одному разу все числа от 1 до  n + 1.  Прибавив к обеим частям сумму  2b1 + 2b2 + ... + 2bk,  получим  11111 + 2(2b1 + 2b2 + ... + 2bk) = 2n+1 – 1,  или
5556 + 2b1 + 2b2 + ... + 2bk = 2n = 1 + 20 + 21 + ... + 2n–1.  Следовательно,  5555 = 2c1 + 2c2 + ... + 2cn–k ,  где c1, c2, ..., cn–k – целые числа от 0 до  n – 1,  отличные от чисел b1, b2, ... , bk.
  5555 = 4096 + 1024 + 256 + 128 + 32 + 16 + 2 + 1 = 212 + 210 + 28 + 27 + 25 + 24 + 21 + 20  (как известно, такое разложение по степеням двойки единственно). Поскольку число 16 здесь есть, то среди чисел 2b1, ... , 2bk его нет. Следовательно, оно среди чисел 2a1, ... , 2ap, то есть 16-граммовая гиря лежит на левой чаше весов.


Ответ

На левую.

Замечания

6 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2000/2001
Номер 22
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .