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


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

Име­ет­ся 288 внеш­не оди­на­ко­вых монет ве­са­ми 7 и 8 грамм (есть и те, и дру­гие). На чаши весов по­ло­жи­ли по 144 мо­не­ты так, что весы в рав­но­ве­сии. За одну опе­ра­цию можно взять с чаш любые две груп­пы из оди­на­ко­во­го числа монет и по­ме­нять их ме­ста­ми. До­ка­жи­те, что можно не более, чем за 11 опе­ра­ций сде­лать так, чтобы весы не были в рав­но­ве­сии.

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

Ре­ше­ние.

Будем ме­нять груп­пы монет с раз­ных чаш. Пусть у нас при каж­дой из сле­ду­ю­щих замен рав­но­ве­сие со­хра­ня­ет­ся. По­ме­ня­ем по одной мо­не­те. Они оди­на­ко­вы. По­ме­ня­ем одну из этих монет с новой. Те­перь три мо­не­ты оди­на­ко­вы: пара на одной и одна  — на дру­гой чаше. По­ме­ня­ем эту пару с парой еще не­тро­ну­тых. Те­перь на одной чаше пара оди­на­ко­вых, на дру­гой  — трой­ка таких же монет. По­ме­ня­ем трой­ку с трой­кой не­тро­ну­тых. Те­перь на одной чаше трой­ка оди­на­ко­вых монет, на дру­гой  — пять таких же монет. Про­дол­жая в том же духе, после k-го шага по­лу­чим на одной чаше \Phi_k оди­на­ко­вых монет, а на дру­гой  — \Phi_k плюс 1 таких же монет, где \Phi_i  — i-ое число Фи­бо­нач­чи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. Итак, после 11-го шага на одной из чаш все мо­не­ты оди­на­ко­вы. Но тогда они та­ко­вы же и на дру­гой, что по усло­вию не­воз­мож­но.

Спрятать критерии
Критерии проверки:

Если ал­го­ритм ука­зан верно, най­де­но со­об­ра­же­ние с чис­ла­ми Фи­бо­нач­чи, но не­вер­ный ответ из-за ошиб­ки в под­сче­тах (на­при­мер, по­лу­чи­лось что хва­тит 10 шагов) оце­нить ре­ше­ние в 4 балла.