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


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

Даны 2019 не­раз­ли­чи­мых по виду монет. Все мо­не­ты имеют оди­на­ко­вую массу, за ис­клю­че­ни­ем одной, более лег­кой. За какое наи­мень­шее число взве­ши­ва­ний можно га­ран­ти­ро­ван­но найти более лег­кую мо­не­ту при по­мо­щи ча­шеч­ных весов без гирь?

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

Ре­ше­ние.

Ин­дук­ци­ей по k до­ка­жем сле­ду­ю­щее утвер­жде­ние: если даны N оди­на­ко­вых по виду монет, при­чем 3 в сте­пе­ни левая круг­лая скоб­ка k минус 1 пра­вая круг­лая скоб­ка мень­ше N мень­ше или равно 3 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка , из ко­то­рых одна более лег­кая, то ее можно найти за k взве­ши­ва­ний. База ин­дук­ции: k=0, N=1, одну мо­не­ту взве­ши­вать не надо. Шаг ин­дук­ции: пусть для 0, 1, 2, \ldots, k до­ка­за­но. Пусть те­перь 3 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка мень­ше N мень­ше или равно 3 в сте­пе­ни левая круг­лая скоб­ка k плюс 1 пра­вая круг­лая скоб­ка . По­ло­жим на левую чашу весов не менее  дробь: чис­ли­тель: N, зна­ме­на­тель: 3 конец дроби монет, но не более 3 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка монет, и на пра­вую столь­ко же. Если левая чаша легче, если левая чаша легче, то лег­кая мо­не­та на ней, если пра­вая  — то на ней, а если весы урав­но­ве­ше­ны, то более лег­кая мо­не­та на­хо­дит­ся среди остав­ших­ся, число ко­то­рых мень­ше или равно  дробь: чис­ли­тель: N, зна­ме­на­тель: 3 конец дроби мень­ше или равно 3 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка . В ре­зуль­та­те, нам оста­нет­ся ис­кать более лег­кую мо­не­ту среди не более 3 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка монет, и по­тре­бу­ет­ся еще не более k взве­ши­ва­ний. По­сколь­ку 3 в сте­пе­ни левая круг­лая скоб­ка 6 пра­вая круг­лая скоб­ка мень­ше 2019 мень­ше или равно 3 в сте­пе­ни левая круг­лая скоб­ка 7 пра­вая круг­лая скоб­ка , то число взве­ши­ва­ний k равно 7.

 

Ответ: 7.