Задача про таблетки и злого гения

Решим ещё одну зада­чу с тести­ро­ва­ни­ем чего-нибудь на мышах! Или на весах! Ещё одна зада­ча из арсе­на­ла при­ни­ма­ю­щих на рабо­ту и про­сто пра­виль­ная гим­на­сти­ка для моз­га. Теперь усло­вия такие:

  • есть 20 бано­чек с таблетками;
  • в одной из них отрав­лен­ные таблетки;
  • таб­лет­ки из насто­я­щих банок весят по 1 грамму;
  • таб­лет­ки из одной отрав­лен­ной бан­ки — 1,1 грамма;
  • все бан­ки выгля­дят оди­на­ко­во внут­ри и снаружи;
  • есть очень точ­ные весы, на кото­рых мож­но взве­ши­вать что угод­но в любом количестве.

Как за одно взве­ши­ва­ние най­ти бан­ку с ток­сич­ны­ми таблетками?

Решение

У нас в рас­по­ря­же­нии есть толь­ко одно взве­ши­ва­ние. Это зна­чит, что надо най­ти такой алго­ритм, кото­рый сра­зу даст точ­ный и одно­знач­ный ответ.

Если мы поло­жим на весы одну нор­маль­ную таб­лет­ку, они пока­жут 1 грамм, а если испор­чен­ную — 1,1 грам­ма. Давай­те посмот­рим, что будет, если из каж­дой бан­ки мы возь­мём по одной таб­лет­ке и поло­жим их все на весы:

(19 × 1) + (1 × 1,1) = 20,1.

Отсю­да мож­но сде­лать два важ­ных вывода:

  • нель­зя брать оди­на­ко­вое коли­че­ство таб­ле­ток из каж­дой бан­ки, пото­му что тогда мы не отли­чим бан­ки друг от друга;
  • одна испор­чен­ная таб­лет­ка даёт лиш­ний вес в 0,1 грамма.

Раз нуж­но из каж­дой бан­ки брать какое-то своё коли­че­ство таб­ле­ток, попро­бу­ем сде­лать так:

  • из пер­вой бан­ки возь­мём 1 таблетку;
  • из вто­рой бан­ки — 2 таблетки;
  • из два­дца­той бан­ки — 20 таблеток.

По этой схе­ме у нас полу­чит­ся всего:

1 + 2 + 3 + ... + 19 + 20 = 210 таблеток.

Теперь нам нуж­но учесть лиш­ний вес в 0,1 грам­ма, кото­рый даёт каж­дая испор­чен­ная таб­лет­ка. Полу­ча­ет­ся, что если у нас будет одна такая, то лиш­ний вес соста­вит 0,1 грам­ма, если две — 0,2 грам­ма и так далее. Зная общее коли­че­ство лиш­не­го веса, мож­но будет вычис­лить коли­че­ство испор­чен­ных таблеток:

количество испорченных таблеток = лишний вес / 0,1.

Оста­лось най­ти лиш­ний вес. Для это­го возь­мём 210 таб­ле­ток по нашей схе­ме, взве­сим их, а от резуль­та­та отни­мем 210 — вес всех таб­ле­ток, если бы они были нор­маль­ны­ми и веси­ли по одно­му грам­му каждая.

Как это работает на практике

Напри­мер, у нас отрав­ле­на бан­ка № 14. Раз мы берём из неё по схе­ме 14 таб­ле­ток, кото­рые в сум­ме весят 14 × 1,1 = 15,4 грам­ма, то общий вес всех таб­ле­ток получится:

196 + 15,4 = 211,4 грамма.

Най­дём лиш­ний вес:

211,4 - 210 = 1,4 грамма.

Теперь раз­де­лим его на 0,1, что­бы узнать номер отрав­лен­ной банки:

1,4 / 0,1 = 14.

Как види­те, такой спо­соб дей­стви­тель­но поз­во­ля­ет за одно взве­ши­ва­ние най­ти нуж­ную бан­ку с таблетками.

Ни одной мыши не пострадало!