Сколько останется шаров?, про шарики в коробке Опции Рейтинг

[Доцент]

Нашел следующую задачку. Показалась занятной.

Шары, пронумерованые числами 1,2,3, ... , кладутся в ящик следующим образом. За одну минуту до полудня кладутся шары 1...10, а шар № 1 вынимается обратно. За 1/2 минуты до полудня кладутся шары 11...20, а шар № 2 вынимается обратно. За 1/3 минуты до полудня кладутся шары 21...30, а шар № 3 вынимается обратно, и т.д. Сколько шаров окажется в ящике в полдень?

[panda-pandus]

А теперь чуть усложним

Рассмотрим измененный алгоритм: кладем шары от 1 до 10, и вынимаем обратно 1. Потом кладем шары от 11 до 20 и вынимаем обратно 11. Потом кладем шары от 21 до 30 и вынимаем обратно 21. Очевидно, при таком алгоритме в ящике останется бесконечно много шаров.

Теперь представим, что на каждом шаре наклеено две наклейки: белая и черная. Изначально на обеих наклейках написан порядковый номер шара. Например, первый шар изначально промаркирован наклейками как 1/1, второй как 2/2, и так далее.

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

- Кладем шары от 1/1 до 10/10, вынимаем шар 1/1
- Кладем шары от 11/11 до 20/20, меняем местами две белые наклейки, вынимаем шар 2/11 (а шар 11/2, к которому перешла одиннадцатая белая наклейка, остается)
- Кладем шары от 21/21 до 30/30, вынимаем шар 3/21
- Кладем шары от 31/31 до 40/40, вынимаем шар 4/31

Так как мы только меняем белые наклейки местами, каждый шар (вынутый или оставшийся, неважно) по-прежнему содержит две наклейки: белую и черную. Никак не мог образоваться шар, на котором только черная наклейка, а белой нету.

Все белые наклейки были вынуты. Из этого следует, что в ящике не могло остаться ни одного шара.

Есть бесконечно много черных наклеек, которые гарантированно не были вынуты. Из этого следует, что в ящике осталось бесконечно много шаров.