Question

100 баллов. В волшебной книге злой колдуньи Гингемы все страницы пронумерованы числами, являющимися целыми степенями двойки (1,2,4,8,16, ... причем номера страниц идут по возрастанию и каждая степень встречается ровно один раз . Для того чтобы наслать очередной ураган Гингема вырвала из книги несколько страниц, сложила числа, записанные в них, получила в результате число 12345678 , после чего произнесла заклинание столько раз, сколько вырвала страниц. Чтобы остановить ураган нужно узнать сколько страниц вырвала из книги Гингема . Помогите Элли и ее друзьям найти ответ на этот вопрос

Answer 1

Ответ:

12

Объяснение:

Чтобы получить ответ, нужно представить 12345678 в виде суммы степеней двойки. Если мы переведем это число в двоичную систему систему счисления, будет достаточно посчитать количество единиц.

Для перевода будем последовательно делить число на 2 и выписывать остатки:

12345678 → 6172839 (ост. 0) → 3086419 (1) → 1543209 (1) → 771604 (1) → 385802 (0) → 192901 (0) → 96450 (1) → 48225 (0) → 24112 (1) → 12056 (0) → 6028 (0) → 3014 (0) → 1507 (0) → 753 (1) → 376 (1) → 188 (0) → 94 (0) → 47 (0) → 23 (1) → 11 (1) → 5 (1) → 2 (1) → 1 (0) → 0 (1)

В принципе, количество единиц можно посчитать уже на этом шаге, но можно и записать число в двоичной форме - для этого все остатки нужно переписать в обратном порядке. Получится 101111000110000101001110 - в этом числе 12 единиц

Answer 2

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

Проанализируем суммы первых нескольких степеней двойки: 1 = 2^0 3 = 2^0 + 2^1 7 = 2^0 + 2^1 + 2^2 15 = 2^0 + 2^1 + 2^2 + 2^3 31 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 63 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 127 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6

Мы видим, что каждое новое число получается путем добавления следующей степени двойки к предыдущей сумме и вычитания 1. Таким образом, мы можем использовать эту последовательность для вычисления суммы чисел на страницах книги:

1 + 3 + 7 + 15 + 31 + 63 + 127 + ... = 2^1 - 1 + 2^2 - 1 + 2^3 - 1 + 2^4 - 1 + 2^5 - 1 + 2^6 - 1 + 2^7 - 1 + ...

Теперь мы можем начать с 2^0 = 1 и последовательно добавлять следующую степень двойки, пока сумма не превысит 12345678. Это позволит нам определить, что последней добавленной степенью двойки было 2^13. Теперь мы знаем, что сумма чисел на страницах до 2^13 включительно составляет 16383.

Однако сумма чисел на страницах после 2^13 может быть больше, чем 12345678. Поэтому нам нужно найти разницу между суммой чисел до 2^13 и числом 12345678:

12345678 - 16383 = 12329395

Теперь у нас есть число 12329395, которое представляет собой сумму чисел на страницах, вырванных из книги. Чтобы найти количество вырванных страниц, мы можем произнести заклинание столько раз, сколько было вырвано страниц. Заклинание было произнесено столько раз, сколько страниц было вырвано, поэтому мы можем использовать разницу 12329395 для определения количества страниц:

12329395 = 2^0 + 2^1 + 2^3 + 2^4 + 2^7 + 2^8 + 2^9 + 2^10 + 2^12

Мы видим, что разница 12329395 представляет собой сумму различных степеней двойки, что означает, что было вырвано 9 страниц (так как есть 9 различных степеней двойки в этой сумме).

Таким образом, Элли и ее друзьям нужно найти ответ: 9 страниц было вырвано из книги Гингемы.