Question

Иллюзионист в цирке показывает фокус. У него имеется 50 монет, он раскладывает их в несколько кошельков. После этого зритель из зала называет любое число от 1 до 50, и фокусник отдаёт ему один или несколько кошельков, содержащих в точности названное зрителем количество монет. Как фокуснику нужно разложить монеты по кошелькам, чтобы он мог отдать любое указанное число монет от 1 до 50? Укажите в ответе количество монет в каждом кошельке в виде последовательности чисел, разделённых пробелами. Сумма всех чисел в ответе должна быть равна 50. Чем меньше кошельков вы используете в своём решении, тем больше баллов вы получите.

Answer 1

Фокуснику нужно разложить монеты по кошелькам так, чтобы в каждом кошельке было столько монет, сколько равно степени двойки. То есть, в первом кошельке 1 монета, во втором 2 монеты, в третьем 4 монеты и так далее. Тогда он сможет отдать любое число монет от 1 до 50, используя соответствующую комбинацию кошельков.
Например, если зритель назовёт число 13, то фокусник отдаст ему кошельки с 1, 4 и 8 монетами. Если зритель назовёт число 50, то фокусник отдаст ему все кошельки.
Ответ: 1 2 4 8 16 19
Всего нужно шесть кошельков. Сумма всех чисел в ответе равна 50. Это минимальное количество кошельков, которое нужно для этого фокуса.