сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word
Тип 0 № 6808
i

В ком­на­те на­хо­дит­ся не­сколь­ко детей и куча из 1000 кон­фет. Дети по оче­ре­ди под­хо­дят к куче. Каж­дый по­до­шед­ший делит ко­ли­че­ство кон­фет в куче на ко­ли­че­ство детей в ком­на­те, округ­ля­ет (если по­лу­чи­лось не­це­лое), за­би­ра­ет по­лу­чен­ное число кон­фет и вы­хо­дит из ком­на­ты. При этом маль­чи­ки округ­ля­ют вверх, а де­воч­ки  — вниз. До­ка­жи­те, что сум­мар­ное ко­ли­че­ство кон­фет у маль­чи­ков, когда все вый­дут из ком­на­ты, не за­ви­сит от по­ряд­ка детей в оче­ре­ди.

 

(Мак­сим Дидин)

Спрятать решение

Ре­ше­ние.

Де­ле­ние с остат­ком кучи кон­фет на k детей можно пред­став­лять себе так: мы рас­кла­ды­ва­ем кон­фе­ты на k кучек, ко­то­рые либо оди­на­ко­вы (если оста­ток 0), либо в части кучек кон­фет на 1 боль­ше, чем в осталь­ных (ко­ли­че­ство таких куч равно остат­ку).

Пусть пер­вый ребёнок раз­ло­жит так кон­фе­ты на кучки, рас­по­ло­жив кучи слева на­пра­во по воз­рас­та­нию числа кон­фет в них. Можно счи­тать, что он возьмёт себе пра­вую кучку, если он маль­чик, или левую, если он  — де­воч­ка.

Когда зайдёт сле­ду­ю­щий ребёнок, кон­фе­ты уже будут раз­ло­же­ны на кучки, как если бы он сам делил с остат­ком (ведь и число детей, и число куч умень­ши­лось на 1), и снова маль­чик возьмёт пра­вую кучу, а де­воч­ка  — левую, и т. д. В итоге маль­чи­ки возь­мут все пра­вые кучки в ко­ли­че­стве, рав­ном числу маль­чи­ков, что не за­ви­сит от по­ряд­ка детей в оче­ре­ди.