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


Задания
Версия для печати и копирования в MS Word

В ряд слева на­пра­во лежат n монет. Из­вест­но, что две из них фаль­ши­вые, они лежат рядом, левая весит 9 грам­мов, пра­вая 11 грам­мов, а все остав­ши­е­ся на­сто­я­щие и каж­дая из них весит 10 грам­мов. Мо­не­ты взве­ши­ва­ют на ча­шеч­ных весах, ко­то­рые либо по­ка­зы­ва­ют, груз на какой их двух чашек тя­же­лее, либо на­хо­дят­ся в рав­но­ве­сии, и тогда грузы на обеих чаш­ках имеют оди­на­ко­вый вес. При каком мак­си­маль­ном n можно за три взве­ши­ва­ния найти мо­не­ту весом 11 грам­мов?

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

Ре­ше­ние.

Пусть n  =  28. Разобьём все монет 28 на три кучи, пер­вая  — мо­не­ты с но­ме­ра­ми 11, 13, 15, 17, 19, 21, 23, 25, 27, вто­рая  — мо­не­ты с но­ме­ра­ми 12, 14, 16, 18, 20, 22, 24, 26, 28, тре­тья  — мо­не­ты с но­ме­ра­ми с 1 по 10. Пер­вым взве­ши­ва­ни­ем срав­ни­ва­ем первую и вто­рую две кучи. За­ме­тим, что, если весы не в рав­но­ве­сии, то тяжёлая мо­не­та в тяжёлой куче. Дей­стви­тель­но, если но­ме­ра обеих фаль­ши­вых монет боль­ше 10, то лёгкая попадёт в одну из двух взве­ши­ва­е­мых куч, а тяжёлая  — в дру­гую и та пе­ре­ве­сит. Если но­ме­ра обеих фаль­ши­вых монет не боль­ше 10, то обе по­па­дут в тре­тью кучу и весы оста­нут­ся в рав­но­ве­сии. Если но­ме­ра фаль­ши­вых монет равны 10 и 11, то тяжёлая попадёт в первую кучу, а вто­рая будет пол­но­стью со­сто­ять из на­сто­я­щих монет и пер­вая пе­ре­ве­сит. Важно от­ме­тить, что, если де­лать ана­ло­гич­ное раз­би­е­ние по по­ряд­ку не с конца но­ме­ров, а сна­ча­ла, то это не­вер­но, когда фаль­ши­вые мо­не­ты лежат на 18-ом и 19-ом ме­стах. Если же весы в рав­но­ве­сии, то тяжёлая и лёгкая мо­не­ты в тре­тьей куче из 10 монет. В этом, «худ­шем», слу­чае разобьём тре­тью кучу ана­ло­гич­но на три: в пер­вой но­ме­ра 6, 8, 10, во вто­рой но­ме­ра 5, 7, 9, в тре­тьей но­ме­ра 1, 2, 3, 4. Вто­рым взве­ши­ва­ни­ем срав­ни­ва­ем первую и вто­рую кучи и вы­яс­ня­ем, в какой из трёх куч тяжёлая мо­не­та те­перь. Если снова ра­вен­ство и она вме­сте с лёгкой снова в тре­тьей куче из 4 монет, срав­ни­ва­ем мо­не­ты 3 и 4. При ра­вен­стве  — тяжёлая 2-ая, если одна тя­же­лее  — та и тяжёлая. То же самое, если тяжёлая в куче из 3 монет  — срав­ни­ва­ем вто­рую и тре­тью, ко­то­рая тя­же­лее  — та и тяжёлая.

Если в пер­вом взве­ши­ва­нии тяжёлая мо­не­та ока­жет­ся, ска­жем, в пер­вой куче, раз­би­ва­ем её на три по три: в пер­вой мо­не­ты 19, 23, 27, во вто­рой 17, 21, 25, в тре­тьей 11, 13, 15 и взве­ши­ва­ем первую и вто­рую, на­хо­дим кучу из трёх монет, со­дер­жа­щую тяжёлую. По­след­ним взве­ши­ва­ни­ем вто­рой и тре­тьей в этой куче на­хо­дим ис­ко­мую. Ана­ло­гич­но, если при пер­вом взве­ши­ва­нии тяжёлая мо­не­та ока­жет­ся во вто­рой куче. От­ме­тим, что лёгкая мо­не­та участ­ву­ет в тре­тьем взве­ши­ва­нии тогда и толь­ко тогда, когда в двух пер­вых имеет место ра­вен­ство. Если монет будет боль­ше 28, то воз­мож­ных по­ло­же­ний для тяжёлой мо­не­ты будет боль­ше 27  =  33, что боль­ше числа воз­мож­ных ис­хо­дов при трёх взве­ши­ва­ни­ях, рав­но­го 3 умно­жить на 3 умно­жить на 3. По­это­му нель­зя од­но­знач­но со­по­ста­вить номер тяжёлой мо­не­ты опре­делённому ис­хо­ду трёх взве­ши­ва­ний и найти её.

 

Ответ: 28.

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

Ал­го­ритм на­хож­де­ния тяжёлой мо­не­ты при n = 28: 5 бал­лов. Если про­из­во­дят­ся ана­ло­гич­ные ука­зан­ным в ав­тор­ском ре­ше­нии раз­би­е­ния, но с на­ча­ла но­ме­ров, а осталь­ное так же: сни­ма­ем 2 балла. При вер­ном раз­би­е­нии нет яв­но­го объ­яс­не­ния того, что, если при пер­вом взве­ши­ва­нии весы не в рав­но­ве­сии, то тяжёлая мо­не­та в тяжёлой куче: сни­ма­ем 1 балл. До­ка­за­тель­ство того, что при n > 28 тяжёлую мо­не­ту нель­зя об­на­ру­жить с га­ран­ти­ей за три взве­ши­ва­ния: 2 балла.