Фильтр
Задачи
Задача 66325 |
|
|
В ряд лежат 100 внешне одинаковых монет. Среди них ровно 26 фальшивых, причём они лежат подряд. Настоящие монеты весят одинаково, фальшивые – не обязательно одинаково, но они легче настоящих. Как за одно взвешивание на двухчашечных весах без гирь найти хотя бы одну фальшивую монету?
Решение
Рассмотрим 26-ю, 52-ю и 78-ю монеты. Ясно, что среди них ровно одна фальшивая. Сравнение любых двух из трёх монет выявит её.
|
|
Задача 66545 |
|
|
Решение
Пример.
| Какие гири покупаем | Что взвешиваем | Сколько монет мы заплатили |
|---|---|---|
| 1 | 1=1 | 100 |
| 2 | 1+2=3, 2=2 | 200 |
| 4 | 2+4=6 | 300 |
| 1 | 1+2+4=7, 1+4=5, 4=4 | 400 |
| 8 | 4+8=12 | 500 |
| 1 | 1+4+8=13 | 600 |
| 2 | 1+2+4+8=15, 2+4+8=14, 2+8=10 | 700 |
| 1 | 1+2+8=11, 1+8=9, 8=8 | 800 |
Оценка. Переходя к каждому взвешиванию, мы либо покупаем одну или несколько гирек, либо отдаём их продавцу. Поэтому мы в сумме купили и отдали N≥15 гирек. При этом после последнего взвешивания у нас на руках есть хотя бы одна гирька, так что мы купили больше, чем отдали. Это значит, что мы купили более половины от N, т. е. как минимум 8 гирек, а значит, заплатили жадному продавцу не менее 800 монет.
Оценка (другой способ.) Представим себе, что плата за каждую гирьку разделена на две части: 50 монет покупатель платит, когда берёт гирьку, а ещё 50 — когда отдаёт. Если считать, что в конце все гирьки возвращаются продавцу, то при таком способе расчёта суммарная плата не изменится.
Рассмотрим 16 моментов: начало, когда покупатель берёт первые гирьки, 14 интервалов между взвешиваниями, и конец, когда покупатель отдаёт оставшиеся гирьки. В каждый из этих моментов покупатель производит какое-нибудь действие (что-то берёт или что-то отдаёт), поэтому должен заплатить не менее 50 монет, а всего ему придётся заплатить не менее 50·16 = 800 монет.
Комментарий. Из решения видно, что оптимальный порядок взвешивания перебирает все возможные наборы гирек, причём соседние наборы отличаются добавлением или удалением ровно одной гирьки. Такая последовательность наборов называется кодом Грея.
Зачем были придуманы коды Грея? Представьте себе, что нам почему-то хочется знать положение вращающегося диска. Если его хочется знать совсем приблизительно, то можно покрасить одну половину диска в чёрный цвет, а другую в белый и поставить фотодатчик. Теперь мы всегда знаем, какой половиной диск повёрнут к датчику.
Но пусть мы хотим большей точности. Можно поставить несколько фотодатчиков и покрасить на диске несколько колец, а в каждом секторе написать его номер чёрными и белыми полосами как двоичным кодом (см. рис. слева).
Но тогда на границе секторов датчики могут сработать не совсем одновременно, и между 001 и 010 мы «увидим» 011 или 000. Для такой ситуации и были придуманы коды Грея: если на границе двух секторов меняется цвет только одного из колец, то в любом случае получить можно только код одного из этих секторов.
Любое оптимальное решение задачи оказывается кодом Грея для 4 колец и 16 секторов (на рис. справа использован код Грея из решения задачи).
Ответ
800 монет.|
|
|
Задача 66763 |
|
|
Как ему за два действия с весами получить кучку, в которой ровно 26 кг песка? Смешать две кучки песка, а также просто ставить что-то на весы действием не считается.
Решение
Первым действием золотоискатель может поставить на левую чашу весов весь песок, а на правую обе гири – и пересыпать песок до достижения равновесия. В~итоге он получит $20$ кг песка слева и $17$ кг песка (и две гири $1+2$ кг) справа. Вторым действием следует на левую чашу весов поставить $20$ кг песка, а на правую гирю в $2$ кг – и вновь уравнивать весы, пока слева не окажется $11$ кг, а справа $9$ кг песка (и одна гиря весом $2$ кг). Наконец, следует смешать полученную вторым действием кучу весом $9$ кг и оставшуюся от первого действия кучу весом в $17$ кг.|
|
|
Задача 66891 |
|
|
Решение
Первые три взвешивания такие: разбиваем гири на две пары способом, который ещё не встречался, и сравниваем их. Разных способов как раз три. Мы получим равенство для пар {1001, 1005} и {1002, 1004}. При этом только гиря 1001 в двух других взвешиваниях была в «лёгкой» паре и только гиря 1005 в двух других взвешиваниях была в «тяжёлой» паре — так находим их. Оставшиеся две гири 1002 и 1004 различаем четвёртым взвешиванием.Ответ
может.|
|
|
Задача 67068 |
|
|
На Поле Чудес выросло 8 золотых монет, но стало известно, что ровно три из них фальшивые. Все настоящие монеты весят одинаково, все фальшивые тоже, но они легче настоящих. Лиса Алиса и Буратино собрали монеты и стали их делить. Алиса собирается отдать Буратино три монеты, но он хочет сначала проверить, все ли они настоящие. Сможет ли он сделать это за два взвешивания на чашечных весах без гирь?
Решение
Пусть сначала Буратино сравнит три свои монеты с тремя монетами Алисы. Если его чаша окажется легче, то у него есть фальшивые монеты. В случае равновесия – тоже есть, поскольку настоящих монет всего пять.
Пусть чаша Буратино тяжелее (то есть на чаше Алисы фальшивых монет больше). Тогда он заменит две монеты с чаши Алисы на ещё неиспользованные. Если и теперь чаша Буратино перевесит, то все монеты у него настоящие: иначе оба раза на чаше Алисы было по две фальшивые монеты, что невозможно. В противном случае, как показано выше, какие-то из монет Буратино фальшивые.
Ответ
Сможет.
|
|
|
Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 152]
