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

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

Как логи­ка и огра­ни­че­ния помо­га­ют най­ти бан­ку с отрав­лен­ны­ми таб­лет­ка­ми.

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

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

Реше­ние

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

Если мы поло­жим на весы одну нор­маль­ную таб­лет­ку, они пока­жут 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.

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

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

Ещё по теме