Игры без компьютера

1000 орехов и 10 кувшинов

Загадка: Имеем 1000 штук грецких орехов и 10 кувшинов. Необходимо разместить орехи по кувшинам таким образом что бы при необходимости можно было бы продать любое количество орехов не вынимая их из кувшинов. Даже если кто--то захочет купить один орех.
Дано: 1000 орехов и 10 кувшинов

Вопрос: Как разместить орехи по кувшинам таким образом, чтобы при необходимости можно было бы продать любое количество орехов, не вынимая их из кувшинов. Даже если кто-то захочет купить один орех.

Решение
Пронумеруем кувшины: X, IX, VIII, VII, VI, V, IV, III, II, I
Разместим орехи по кувшинам так:
в X кувшин – 489 орехов = 1000 - 511. 511 = сумма орехов в девяти кувшинах с I по IX
в IX – 256 = 2^8
в VIII – 128 = 2^7
в VII – 64 = 2^6
в VI – 32 = 2^5
в V – 16 = 2^4
в IV – 8 = 2^3
в III – 4 = 2^2
во II – 2 = 2^1
в I кувшин – 1 орех = 2^0

Если нужно от 1 до 488 орехов – они в нескольких кувшинах с номерами от I до IX.
Если нужно 489 орехов – они в кувшине X.
Если число орехов не меньше 490 и не больше 1000, то используем кувшин X, в котором 489 орехов. и для остатка (остаток м.б. от 1 = 490 - 1 до 511 = 1000 - 489) – подбираем кувшины от I до IX.

Как любое число от 1 до 511 разложить на сумму чисел, каждое из которых равно какой-либо степени числа два?

Есть несколько способов
Один из них - записать число в двоичной системе.
Например, 389 в десятичной системе исчисления равно числу 110000101 в двоичной системе исчисления.
Степени двойки, из которых число 389 складывается, - они отражаются позициями единиц в двоичном представлении:
110000101 – единицы в позициях 0, 2, 7, 8 (нумерация позиций идет справа налево, при этом нумерация берет начало с 0). Значит, 389 = 2^0 + 2^2 + 2^7 + 2^8 = 1 + 4 + 128 + 256
То есть, для получения 389 орехов, нужно взять кувшины I, III, VIII и IX
Если нужно, допустим, продать 931 орех, то 931 – 489 (число орехов в кувшине X) = 442
442 в десятичной системе исчисления равно числу 110111010 в двоичной системе исчисления. В этом числе 110111010 – единицы в позициях 1, 3, 4, 5, 7, 8. Значит, 442 = 2^1 + 2^3 + 2^4 + 2^5 + 2^7 + 2^8 = 2 + 8 + 16 + 32 + 128 + 256
То есть, для получения 931 ореха, нужно взять кувшины II, IV, V, VI, VIII, IX и X

Для того, чтобы преобразовать число из 10-й системы счисления в 2-ную, необходимо выполнить следующие действия.
1. Делить десятичное число на 2 и записываем остаток от деления.
2. Результат деления вновь делить на 2 и опять записываем остаток.
3. Повторять операцию до тех пор, пока результат деления не будет равен нулю.
4. Записать полученные остатки в обратном порядке и получить искомое число.
Например, перевод числа 442 из десятичной системы в двоичную:
442/2 = 221 (остаток 0)
221/2 = 110 (ост. 1)
110/2 = 55 (ост. 0)
55/2 = 27 (ост. 1)
27/2 = 13 (ост. 1)
13/2 = 6 (ост. 1)
6/2 = 3 (ост. 0)
3/2= 1 (ост. 1)
1/2 = 0 (остаток 1)
Значит, 442 в 10-й системе исчисления равно числу 110111010 в 2-й системе.

Если не хотите переводить число из 10-ной в 2-ную систему, то есть иной метод разложения заданного числа на сумму чисел, каждое из которых равно какой-либо степени числа два.
Для этого на каждом шаге необходимо подобрать максимальную степень двойки, меньшую либо равную текущему числу. Запомнить это число, как одно из слагаемых и отнять от числа. Повторять до тех пор, пока число не станет равным 0.
Например, 442
Максимальная степень двойки, меньшая или равная 442 - 256. Запоминаем 256, отнимаем его от 442, получаем 186.
Макс. ст. двойки, меньшая или равная 186 - 128. Запоминаем 128, отнимаем его от 186, получаем 58.
Макс. ст. двойки, меньшая или равная 58 - 32. Запоминаем 32, отнимаем его от 58, получаем 26.
Макс. ст. двойки, меньшая или равная 26 - 16. Запоминаем 16, отнимаем его от 26, получаем 10.
Макс. ст. двойки, меньшая или равная 10 - 8. Запоминаем 8, отнимаем его от 10, получаем 2.
Макс. ст. двойки, меньшая или равная 2 - 2. Запоминаем 2, отнимаем его от 2, получаем 0.
Вот и все, разложение закончено, и в итоге 442 = 256 + 128 + 32 + 16 + 8 + 2.

P.S. "В действительности всё выглядит иначе, чем на самом деле" © Станислав Ежи Лец
Маша Кракату
Маша Кракату
35 151
Лучший ответ
Рома Бабровский Шикарный ответ!
Ну значит в первый кувшин один орешек. Во второй - два и тд
Рома Бабровский кувшинов всего 10.
Ананасы будут?
Размещаем орехи по 100 в каждом кувшине, тогда мы получим 1000 орехов, разбитых по 10 кувшинам. Теперь, если кто-то захочет купить один орех, мы можем просто взять его из любого кувшина, не нарушая условия.
Рома Бабровский Орехи продаются в месте с кувшинами.