Question

Вася взял газетный лист. Он может проделывать следующую операцию: брать любой газетный кусок и разрывать его на 5 или на 9 кусков. Cколько кусков Вася может получить, проделав описанную операцию 100 раз? Ответы: 301 302 303 504 505 506 707 708 709 901 902 903

Answer 1

Ответ:

505, 709

Пошаговое объяснение:

Операция первого типа увеличивает количество кусков на 4, второго типа - на 8. Пусть Вася рвал куски на 5 частей n раз, а на 9 частей, соответственно, 100 - n раз. Тогда общее количество кусков окажется равным 1 + 4n + 8(100 - n) = 801 - 4n, где n может принимать значения 0, 1, 2, ..., 100. Значит, Вася может получить любое количество кусков от 801 - 400 = 401 до 801, если оно даёт остаток 1 при делении на 4.

X 301  - меньше 401

X 302  - меньше 401

X 303  - меньше 401

X 504  - четное

V 505  - подходит, 801 - 4n = 505 при n = 74

X 506  - четное

X 707  - остаток 3 при делении на 4

X 708  - четное

V 709  - подходит, 801 - 4n = 709 при n = 23

X 901  - больше 801

X 902   - больше 801

X 903  - больше 801

Answer 2

Для решения этой задачи можно использовать рекурсивный подход. Пусть функция count_pieces(n) возвращает количество кусков, которые можно получить, если проделать описанную операцию n раз.

Начальное значение: count_pieces(0) = 1 (исходный газетный лист).

Далее, используя рекурсию:

• Если n делится на 5 или 9 без остатка, то можно разорвать предыдущий лист на 5 или 9 кусков соответственно и применить count_pieces(n-1) к каждому куску. Таким образом, count_pieces(n) = 5 * count_pieces(n-1) или count_pieces(n) = 9 * count_pieces(n-1).
• Если n не делится ни на 5, ни на 9 без остатка, то можно только применить count_pieces(n-1) к предыдущему листу. Таким образом, count_pieces(n) = count_pieces(n-1).

Теперь можем вычислить count_pieces(100):

scssCopy code
count_pieces(0) = 1

count_pieces(1) = count_pieces(0) = 1
count_pieces(2) = count_pieces(1) = 1
count_pieces(3) = count_pieces(2) = 1
count_pieces(4) = count_pieces(3) = 1
count_pieces(5) = 5 * count_pieces(4) = 5
count_pieces(6) = count_pieces(5) = 5
count_pieces(7) = count_pieces(6) = 5
count_pieces(8) = count_pieces(7) = 5
count_pieces(9) = 9 * count_pieces(8) = 45
count_pieces(10) = 5 * count_pieces(9) = 225
count_pieces(11) = count_pieces(10) = 225
count_pieces(12) = count_pieces(11) = 225
...
count_pieces(99) = count_pieces(98) = 901
count_pieces(100) = 5 * count_pieces(99) = 5 * 901 = 4505

Таким образом, количество кусков, которые можно получить, проделав описанную операцию 100 раз, равно 4505.

Среди предложенных ответов только один совпадает с этим результатом: 4505.