Бинарная система счисления.

Постановка задачи о взвешивании на рычажных весах с одной чашей для гирь

Пусть задан набор из конечного числа натуральных чисел, которые иногда будем называть "набором гирь"
Будем считать, что набор гирь используется на взвешивания на "рычажных" весах, в которых одна чаша используется для груза, а вторая для гирь.
"Взвесить" груз будет означать, что в наборе гирь надо найти подмножество гирь, что их суммарный вес равен весу груза (считается, вес груза есть натуральное число)
Например:
Пусть задан набор гирь A = {1, 1, 1, 3, 8}
Мы сможем взвесить грузы весом в 1, 2, 3, 4, 5, 6, 8, 9,,10, 11, 12, 13, 14 у.е. (условных единиц), но
груз весом в  7 у.е. взвесить не сможем (хотя груз весом 3 у.е. сможем взвесить двумя способами)

Определение Набор гирь A = {a₁, ..., a_k} назовем универсальным, если он позволяте взвесить все веса от 1 до sum(A), где sum(A) есть сумма весов всех гирь.

Попробуем найти решение нескольких "Проблем":

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

2. Каким должен быть "эффективный" набор гирь. "Эффективный" это:

• универсальный

• при заданном числе гирь имеющий максимальную сумму гирь

• при заданной сумме гирь содержащий наименьшее количество гирь

Решим проблему I.

Пусть задан набор гирь A с sum(A) = N, к которому добавляется гиря весом X
Все подмножества  множества A + {X} можно разбить на три непересекающихся кластера:

• подмножества, состоящие только из элементов A - можно получить N различных весов

• подмножество из одного X - можно получить только один вес

• подмножества, в которые входит X и натуральное(ненулевое) количество элементов из А - можно получить N различных весом

Таким образом, можно получить не более 2N + 1 различный вес ( N + 1 + N). Новый набор должен быть универсальным, значит надо уметь получать веса 1, 2, .... Из этого следует, что суммарный вес нового набора не превосходит 2N + 1 (это "оценка")
Нетрудно заметить, что положить X равным N+1, то "оценка" будет достигаться.
Можно считать, Проблема I решена и определено следующее правило "эффективного добавления гири к универсальному набору"

Если есть универсальный набор гирь с суммарным весом N, то добавление гири весом N +1 позволит получить универсальный набор с максимально возможной суммой

 

 

Построение универсальных наборов по правилу "эффективного" добавления.

Из 1 гири существует только 1 универсальный набор A₁ = {1}  и sum(A₁) = 1
Следующая гиря должна быть весом sum(A₁) + 1 = 2. А₂ = {1,2} и  sum(A₂) = 3
далее получим гиру весом 3 + 1 = 4 и т.д...
Можно заметить, что если A_k ={a₁, a₂, ..., a_k} то

• a_i = 2^i-1
• sum(A_k) = 2ⁱ - 1

(достаточно доказать/показать, что 2⁰ + 2¹ + ... + 2^k = 2^k+1 - 1 - это можно сделать индукцией и любым другим способом)
Это правило можно описать системой рекурсий  для натуральных чисел
W(n) = 1 при n = 1
S(n) = 1 при n = 1
W(n) = S(n - 1) + 1 при n > 1
S(n) = S(n - 1) + W(n) при n > 1

Указанный способ построения практически является доказательством того, что 
наборы вида {1, 2, 4, ..., 2k} и есть "эффективные наборы гирь" для модели "рычажных весов с одной чашей для гирь.

Следствие: Любое натуральное число может быть представлено в виде суммы степеней числа 2, причем в единственном виде

 

"Эффективный набор гирь", предстваление числа в бинарной записи, игра "Угадай число" и количество информации.

Пусть есть "эффективный набор гирь" состоящий из 10 гирь: (1, 2, 4, 8, 16, 32, 64, 128, 256, 512}
Попробуем ответить на вопросы:

1.  Какой максимальный вес можно взвесить этим набором
2. Пусть надо взвесить некоторое неизвестное X. 
   1. Какую гирю надо поставить на весы первой, второй .... (чаша вначале пустая)
   2. Сколько "испытаний/перестановок гирь" придется сделать
   3. Как записать результаты взвешивания
   4. Как по результатам взвешивания установить вес
3. Нам известно значение X, но мы хотим определить набор гирь, уравновешивающий его
   1. С какой чашей (полной или пустой) будет удобнее начинать?
   2. Можно ли определить понятие "дополняющий вес"

Итак, мы научились взвешивать груз.  Попробуем сыграть в игру "Угадай число"
Правила игры -

• Соперник загадывает некоторое число X  от 1 до N (8, 10, 100, 1000, 1 000 000). Число N известно Игроку
• Игрок задает вопрос, на который Соперник отвечает Да или Нет
• Игра заканчивается, когда игрок называет загаданное число не задавая вопроса

Пример протокола игры (при N = 4)

• Игрок - "Это число равно 1"   Соперник "Нет"
• Игрок - "Это число равно 2"   Соперник "Нет"
• Игрок - "Это число равно 3"   Соперник "Нет"
•  Игрок - "Загадано число 4"
  игра завершилась и Игрок задал три вопроса

Практика перевода чисел в двоичную систему методом взвешивания

 

Число/остаток		206	78	14	6	2	0	запись	512	256	128	64	32	16	8	4	2	1
718	512	128	64	8	4	2			1	0	1	1	0	0	1	1	1	0

Число/остаток		81	17	1	0	запись	256	128	64	32	16	8	4	2	1
337	256	64	16	1			1	0	1	0	1	0	0	0	1

запись	512	256	128	64	32	16	8	4	2	1
1011001110	1	0	1	1	0	0	1	1	1	0	2 + 4 + 8 + 64 + 128 + 512 = 718

Взвесить 251? 
А если воспользоваться тем, что 251 = 255 -4 ? Почему 255?