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


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

Есть 100 внеш­не не­раз­ли­чи­мых монет трёх типов: зо­ло­тые, се­реб­ря­ные и мед­ные (каж­дый тип встре­ча­ет­ся хотя бы раз). Из­вест­но, что зо­ло­тые весят по 3 грам­ма, се­реб­ря­ные  — по 2 грам­ма, мед­ные  — по 1 грам­му. Как на ча­шеч­ных весах без гирек га­ран­ти­ро­ван­но опре­де­лить тип у всех монет не более, чем за 101 взве­ши­ва­ние?

 

(Вла­ди­слав Но­ви­ков)

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

Ре­ше­ние.

I спо­соб. (А. Ша­по­ва­лов) Назовём си­ту­а­цию по­бед­ной, если про­ве­де­но не более чем k плюс 1 взве­ши­ва­ние и опре­де­ле­ны веса k монет, причём среди них есть се­реб­ря­ная или две мед­ных. В по­бед­ной си­ту­а­ции, срав­ни­вая не­из­вест­ную мо­не­ту с весом 2 г, мы опре­де­лим её вес, уве­ли­чив число из­вест­ных монет и число взве­ши­ва­ний на еди­ни­цу и так опре­де­лим все мо­не­ты не более чем за 101 взве­ши­ва­ние.

В каж­дый мо­мент будем срав­ни­вать число за­тро­ну­тых (участ­во­вав­ших во взве­ши­ва­ни­ях) монет z \mathrmc чис­лом взве­ши­ва­ний v . Сна­ча­ла вы­де­лим одну мо­не­ту и будем срав­ни­вать не­за­тро­ну­тые мо­не­ты с ней, пока не найдём мо­не­ту дру­го­го веса. Пусть A более лёгкая, а B  — более тяжёлая из за­тро­ну­тых монет. Далее срав­ни­ва­ем не­за­тро­ну­тые мо­не­ты с B, пока снова не по­лу­чим не­ра­вен­ство. Те­перь у нас v=z минус 1; есть одна или не­сколь­ко монет оди­на­ко­во­го веса a, одна или не­сколь­ко монет дру­го­го веса b боль­ше a и одна мо­не­та C веса c не равно q b. Срав­ним C с A. Воз­мож­ны два слу­чая.

1)  Если c=a. Срав­ним B с A плюс C, то есть b с 2 a. Воз­мож­ны ва­ри­ан­ты: b=3, a=1 (если b боль­ше 2a пра­вая круг­лая скоб­ка ; b=2, a=1 левая круг­лая скоб­ка b=2 a пра­вая круг­лая скоб­ка ; b=3, a=2 левая круг­лая скоб­ка b мень­ше 2 a пра­вая круг­лая скоб­ка . Во всех слу­ча­ях си­ту­а­ция по­бед­ная: v=z плюс 1, веса z монет опре­де­ле­ны и есть нуж­ные мо­не­ты (с общим весом 2).

2)  Если c не равно q a . Зна­чит, a, b, c  — три раз­ных веса, они как-то упо­ря­до­че­ны  левая круг­лая скоб­ка c боль­ше b боль­ше a, b боль­ше c боль­ше a или b боль­ше a боль­ше c пра­вая круг­лая скоб­ка , по­это­му опре­де­ле­ны од­но­знач­но. При этом v=z  — си­ту­а­ция по­бед­ная.

За­ме­ча­ние. При опре­де­лен­ных усло­ви­ях не­ко­то­рые взве­ши­ва­ния можно не про­во­дить: на­при­мер, если C тя­же­лее B, то уже c боль­ше b боль­ше a; если при пер­вом не­ра­вен­стве уже есть ещё мо­не­та веса a, ей можно вос­поль­зо­вать­ся как мо­не­той C.

 

II спо­соб. (A. Ря­би­чев) Сна­ча­ла до­ка­жем по ин­дук­ции сле­ду­ю­щее вспо­мо­га­тель­ное

утвер­жде­ние 1. Пусть есть k монет, среди ко­то­рых все три типа пред­став­ле­ны, причём про пару монет A, a уже из­вест­но, что A боль­ше a. Тогда можно опре­де­лить, какая из k монет ка­ко­го типа, за k минус 1 взве­ши­ва­ние.

База. Если монет три, срав­нив остав­шу­ю­ся мо­не­ту с A и с a, мы упо­ря­до­чим их по весу.

Шас. Срав­ним какие-ни­будь две мо­не­ты, кроме A и a. Если они равны, то одну можно от­бро­сить (за­пом­нив, с какой она сов­па­да­ет по весу), и вос­поль­зо­вать­ся пред­по­ло­же­ни­ем ин­дук­ции для k минус 1 мо­не­ты.

Если они не равны, ска­жем что по­лу­чи­лась пара B боль­ше b. Те­перь срав­ним A плюс a и B плюс b. Если веса пар равны, то A=B и a=b, так что мы можем вы­ки­нуть B и b (за­пом­нив, что они сов­па­да­ют по весу с A и a), и вос­поль­зо­вать­ся пред­по­ло­же­ни­ем ин­дук­ции для k минус 2 монет.

Пусть веса пар раз­лич­ны, для опре­делённо­сти, A плюс a боль­ше B плюс b. За­ме­тим, что при этом обя­за­тель­но A=3 и b=1. Мо­не­ты в паре  левая круг­лая скоб­ка B, a пра­вая круг­лая скоб­ка имеют либо веса (2, 1), либо (2, 2), либо (3, 2). Таким об­ра­зом, срав­нив A плюс b с B плюс a, мы од­но­знач­но вос­ста­но­вим веса всех четырёх монет. Среди них есть мо­не­та веса 2, будем срав­ни­вать с ней все осталь­ные мо­не­ты, на что уйдут остав­ши­е­ся k минус 4 взве­ши­ва­ния. Пер­вое утвер­жде­ние до­ка­за­но. Те­перь вы­ве­дем по ин­дук­ции сле­ду­ю­щее утвер­жде­ние, уси­ли­ва­ю­щее тре­бу­е­мое в за­да­че.

Утвер­жде­ние 2. Если есть k монет, среди ко­то­рых все три типа пред­став­ле­ны, то можно опре­де­лить, какая мо­не­та ка­ко­го типа, за k взве­ши­ва­ний.

База. Если монет три, то, срав­нив каж­дую с каж­дой, мы упо­ря­до­чим их по весу.

Шаг. Срав­ним какие-ни­будь две мо­не­ты. Если они равны, то одну можно от­бро­сить (за­пом­нив, с какой она сов­па­да­ет по весу), и мы пе­ре­хо­дим к слу­чаю k минус 1 мо­не­ты, среди ко­то­рых все типы пред­став­ле­ны. Если они не равны, ска­жем что об­ра­зо­ва­лась пара A боль­ше a и вос­поль­зу­ем­ся утвер­жде­ни­ем.

За­ме­ча­ние. Мы сде­ла­ли на одно взве­ши­ва­ние мень­ше, чем пред­по­ла­га­лось в усло­вии. Кроме того, мы ис­поль­зо­ва­ли толь­ко то, что сумма весов двух се­реб­ря­ных монет равна сумме весов мед­ной и зо­ло­той; тот факт, что се­реб­ря­ная мо­не­та вдвое тя­же­лее мед­ной, для дан­но­го ре­ше­ния не важен.