Question

Дам 30 баллов!!!!Рассмотрим последовательность из нулей и единиц, которая генерируется по следующему правилу. Исходно она состоит из одной единицы (1), На каждом следующем шаге к ней приписывается справа последовательность с предыдущего шага, в которой все нули поменяли на единицы, а единицы на нули. То есть, на первом шаге к ней приписывается 0 (получили 10), на втором шаге приписывается 01 (получили 1001) и так далее. Сколько единиц будет в последовательности после одиннадцатого шага? В качестве ответа укажите одно натуральное число, например, 5.

Answer 1

0. 1
1. 10
2. 1001
3. 10010110
4. 1001011010010110
5. 10010110100101101001011010010110

После четвёртого шага я заметил, что наша строка состоит из подстрок "1001" и "0110". Количество таких подстрок после третьего шага начинает увеличиваться в два раза с каждым шагом. Например, в третьем шаге подстрока"10010110" - одна, а в четвёртом - две. Исходя из этого можно вынести, что в пятом шаге их - четыре (кто сомневается - проверьте). Составим таблицу, благодаря которой мы узнаем, сколько подстрок "10010110" будет в строке после одиннадцатого шага:
3. 1
4. 2
5. 4
6. 8
7. 16
8. 32
9. 64
10. 128
11. 512

После одиннадцатого шага строка будет иметь 512 подстрок "10010110" - то есть, состоять из 512 * 8 = 4096 символов. Это всего лишь отступление.

В одной подстроке "10010110" - 4 единицы. Значит, в 512 таких подстроках их будет 512 * 4 = 2048 штук.

Ответ: 2048.

Answer 2

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

* Шаг 1: 1 (1 единица) * Шаг 2: 10 (1 единица) * Шаг 3: 1001 (2 единицы) * Шаг 4: 10010110 (4 единицы) * Шаг 5: 1001011001101001 (8 единиц) * Шаг 6: 100101100110100100101101001100 (16 единиц) * Шаг 7: 1001011001101001001011010011001001011000110100100101101001100 (32 единицы) * Шаг 8: 1001011001101001001011010011001001011000110100100101101001100100101100110101100101100110101100 (64 единицы) * Шаг 9: 1001011001101001001011010011001001011000110100100101101001100100101100110101100101100110101100101100110100110100110100110100110100110100110100 (128 единиц) * Шаг 10: 1001011001101001001011010011001001011000110100100101101001100100101100110101100101100110101100101100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100 (256 единиц) * Шаг 11: 100101100110100100101101001100100101100011010010010110100110010010110011010110010110011010110010110011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010011010010110100110010010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011010110010110011