Задача 8:

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

Решение:

Любое число можно записать в двоичной системе счисления. Поэтому для взвешивания любого числа граммов от 1 до 100 достаточно иметь семь гирь с весами: 1, 2, 4, 8, 16, 32, 64. Шестью гирями обойтись нельзя, так как с их помощью можно взвесить не более 2⁶ – 1 = 63 различных весов (каждая гиря либо участвует, либо не участвует во взвешивании).

Задача 9:

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

Решение:

При решении этой задачи нам понадобится следующее интересное свойство троичной системы счисления:

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

Для доказательства нужно записать исходное число в троичной системе счисления и построить требуемые числа поразрядно справа налево. При этом если у получившихся чисел в каких-то одноименных разрядах стоят единицы, то их можно заменить нулями.

Теперь понятно, что достаточно иметь 5 гирь с весами 1, 3, 9, 27, 81 (подумайте, почему не нужна гиря весом 243 грамма).

Четырех же гирь явно недостаточно, так как с их помощью можно взвесить не более 3⁴ – 1 = 80 различных весов (каждая гиря либо на левой чашке весов, либо на правой, либо не участвует во взвешивании).

Задача 10:

Кащей Бессмертный загадывает три двузначных числа: a, b и c. Иван Царевич должен назвать ему три числа: X, Y, Z, после чего Кащей сообщит ему сумму aX + bY + cZ. Царевич должен отгадать задуманные числа, иначе ему отрубят голову. Как ему спастись?

Решение:

Царевич должен назвать числа 1, 100, 100² = 10000. Числа a, b, c – «цифры» ответа Кащея в 100-ичной записи.

Задача 11:

Докажите, что из набора 0, 1, 2, …, 3^k – 1 можно выбрать 2^k чисел так, чтобы никакое из них не являлось средним арифметическим двух других выбранных чисел.

Решение:

Воспользуемся троичной системой счисления. Будем считать, что троичная запись каждого из данных чисел состоит ровно из k цифр (при необходимости заполним пустующие старшие разряды нулями). Выберем теперь те числа, троичная запись которых содержит только цифры 0 и 1. Очевидно, что их ровно 2^k. Покажем, что это и есть искомый набор. Предположим противное: среди выбранных чисел есть три различных числа x, y, z, удовлетворяющих равенству x + y = 2z. Так как числа x и y различаются хотя бы в одном разряде, то в троичной записи их суммы x + y в этом разряде стоит цифра 1. Однако в записи числа 2z встречаются только 0 и 2.

Задача 12:

Докажите, что из набора 0, 1, 2, …, 3^k – 1/2 можно выбрать 2^k чисел так, чтобы никакое из них не являлось средним арифметическим двух других выбранных чисел.