Известно, что среди 18 шаров два радиоактивных. Можно проверять на радиоактивность кучку из любых шаров. Как за 8 таких проверок наверняка найти оба радиоактивных шара?

252

461

Посмотреть ответы 2

Ответы на вопрос:

ellLMo

Другие предметы

4,4(48 оценок)

Решение этой головоломки основывается на двух простых соображениях:
1. Для того, чтобы среди 2n шаров найти один радиоактивный, достаточно n проверок. Например, чтобы среди 8 шаров обнаружить один радиоактивный, достаточно 3 проверок. Для этого надо действовать методом деления пополам (или дихотомии): исходное количество шаров разделить на 2 одинаковые кучки и проверить одну из них, затем найденную радиоактивную кучку (если проверяемая кучка не радиоактивная, то радиоактивной будет вторая) снова разделить на две равные кучки и проверить одну из них, и так далее. В конце кучка из двух шаров разделяется на две «кучки» из одного шара, и n-й проверкой находится радиоактивный шар.
2. В радиоактивной кучке из 6 шаров за 3 проверки можно найти радиоактивный шар и ещё как минимум для одного шара определить, радиоактивный он или нет. Для этого надо разделить эту кучку на две равные кучки из 3 шаров и проверить одну из них, а в той кучке, которая окажется радиоактивной, по очереди проверить два любых шара.
Объединив эти два соображения, можно получить следующий алгоритм решения:
1. Проверяем на радиоактивность кучку из 6 любых шаров.
2. Если эта кучка радиоактивна, то за 3 проверки мы можем обнаружить радиоактивный шар и ещё для одного шара определить, является ли он радиоактивным (соображение №2). Если этот шар не является радиоактивным, то возвращаем оставшиеся 4 шара к остальным 12 и среди получившихся 16 шаров за 4 оставшиеся проверки находим второй радиоактивный шар (соображение №1).
3. Если эта кучка из 6 шаров не радиоактивна, то разбиваем оставшиеся 12 шаров на 3 кучки по 4 шара и проверяем каждую из них. Если радиоактивной окажутся две кучки, то для каждой из них достаточно двух проверок для нахождения радиоактивного шара. Если радиоактивной окажется одна кучка, то по очереди проверяем все её шары, пока не найдём два радиоактивных.

Рофлер

Другие предметы

4,5(84 оценок)

Послушайте и прочитайте. Затем ответьте на следующие вопросы: Какие новые хобби Роберт начал во время своего пребывания в США? Чем занимается отец Теда Роджерса?
14767 Sunset Boulevard,
Orlando
Florida
USA
6th April, 2014
Dear Pat, Nevita, Rachel, Trevor (and Scoop),
I’ve been in Orlando for two weeks now, and I’m really enjoying myself! The weather’s great — it’s sunny every day, and it’s really hot. I wish the weather was like this in England. Ted’s a great guy, and we get on really well. Every morning we go swimming in the pool in the garden. Everybody in Ted’s street has got a swimming pool!
Orlando is quite a nice place, but there are too many old people here and not enough young people, and there are lots of English people, too. Ted’s been living here since 2011.
(отрывок из текста)

14767 Бульвар Сансет,
Орландо
Флорида
США
6 апреля 2014
Дорогие Пэт, Невита, Рейчел, Тревор (и Скуп),
Я в Орландо уже в течение двух недель, и я действительно наслаждаюсь! Погода великолепна – каждый день солнечный и действительно жарко. Я бы хотел, чтобы такая погода была в Англии. Тед отличный парень, и мы ладим на самом деле хорошо. Каждое утро мы ходим купаться в бассейне в саду. У каждого на улице Теда есть бассейн!
Орландо довольно хорошее место, но здесь слишком много пожилых людей и не хватает молодых, и здесь также много англичан. Тед живет здесь с 2011 года.
Раньше он жил в Нью-Йорке, но он и его семья переехали сюда, когда его отец начал работать в морском институте. Его папа морской зоолог.
Вчера я был в Центральном зоопарке Флориды и видел крокодила. Завтра мы собираемся в подводное плавание. Тед занимается дайвингом с прошлого года. В данный момент я прохожу курс — это здорово, но я должен изучать теорию каждый день, и я должен сдать экзамен на следующей неделе. Отец Теда изучает жизнь акул. Он изучает акул с тридцати пяти лет, и он является экспертом. Я посылаю вам статью для RAP об акулах.
Даже если у меня хорошее время здесь, я скучаю по вам очень сильно. Я хочу, чтобы вы все были здесь со мной. Увидимся в следующем месяце в Бристоле.
С наилучшими пожеланиями,
Роберт
Hi, Robert. What are you doing? — Привет, Роберт. Что делаешь?
I’m writing a letter to my friends at The RAP. — Я пишу письмо моим друзьям в RAP.
How long have you been working at The RAP? – Как долго ты работаешь в RAP?
I’ve been working there for two years. — Я работаю там в течение двух лет.
Can I read your letter? — Могу ли я прочитать твое письмо?
Yes, of course. Here you are. — Да, конечно. Вот.