Санкт-Петербургская классическая гимназия №610 Для слабовидящих
школаучебалюдипартнерыдосугфотобанкфорум
             

Форум

новое сообщение | поиск | статистика | правила | регистрация

выпускник Юрий Мельников: Google // 12 сентября 2007, 01:14

Тестирование соискателей в компанию Google:

у одного короля была сотня советников. Все они были гномы. Советники давали плохие советы, и король принял решение их казнить.

В день казни гномики были выстроены в очередь. При этом у каждого гнома был на голове колпак черного или белого цвета.

Итак, ситуация такова: Если гном угадывает цвет колпака, который на нём надет, то он выживает, а ежели нет, то ему соответственно голову отрубают.

И еще: Каждый гном видит цвета колпаков впередистоящих гномов.

А также: гном, стоящий на плахе, видит всех остальных. Первым казнят последнего гнома в очереди.

Ах, да, вопрос: Какое максимальное количество гномов выживет?

Ну, и еще, Алексей Вадимович Белецкий полагает, что всё это излишне.

спасибо

Комментировать | Вся дискуссия
учитель Роман Родионов: Я не математик :) // 12 сентября 2007, 03:08

Максимальное - сто. Ну, например, если все угадают.

Комментировать
учитель Дмитрий Кобак: 99 гномов // 12 сентября 2007, 12:28

Ты забыл упомянуть ключевой момент: вся очередь видит, что происходит на плахе (казнят очередного гнома или нет). И еще: гномы не могут обмениваться никакими сигналами.

Я решил задачу вчера по пути домой. Максимум, действительно, 99. Имеется в виду максимум в худшем случае, так что Ромино соображение ("если всем повезёт") не по делу.

Комментировать
учитель Роман Родионов: Почему 99? // 12 сентября 2007, 22:54

А если все 100 угадают?

Комментировать
учитель Дмитрий Кобак: Я же объясняю // 12 сентября 2007, 23:06

Вопрос задачи такой: какое наибольшее число гномов могут ГАРАНТИРОВАННО спастись.

Комментировать
учитель Роман Родионов: А вот и нет! // 13 сентября 2007, 02:00

Вопрос задачи:
"Какое максимальное количество гномов выживет?"
При таком вопросе, правильный ответ - 100. Например, если каждый угадает.

Комментировать
учитель Сергей Чистович: Не надо изображать из себя клоуна // 13 сентября 2007, 11:07

Конечно, задача с самого начала была сформулирована некорректно, но всё-таки понять суть проблемы можно. Мы же не в суде, а?

Комментировать
учитель Роман Родионов: Тогда действительно 99. // 14 сентября 2007, 09:37

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

Комментировать
учитель В. В. Зельченко: И еще одна вещь, которую надо упомянуть: // 12 сентября 2007, 15:12

пока несли колпаки, у гномиков была возможность обсудить ситуацию.
Эта задача, кстати, знаменита в гимназии; по крайней мере, несколько классов знают ее в полном составе.

Комментировать
выпускник Артём Григорьев: Ага 99 // 12 сентября 2007, 17:31

Я её этим летом решил. Там не выжить может только первый.

Комментировать
учитель Александр Симин: Сформулируйте нормально условия задачи... // 14 сентября 2007, 12:48

В отдном посте, а то непонятно, но тоже интересно... :-)
Плиз

Комментировать
учитель В. В. Зельченко: Специально для Вас // 14 сентября 2007, 19:04

Злой волшебник решил изощренно наказать 100 гномов. Он сказал им: "Я расставлю вас в затылок друг другу, сверху вниз на склоне холма, и надену на вас белые и черные колпаки (сколько каких колпаков - не скажу). Потом я буду подходить к каждому из вас по очереди, начиная с последнего, и спрашивать: "Какой на тебе колпак?" Отвечать можно только "Белый" или "Черный"; будете кашлять, шаркать или еще как-нибудь подавать знаки - сразу же съем всех. Если гном угадает, я его помилую; если назовет неправильный цвет - проглочу". Сказав это, волшебник ушел за колпаками, а гномы в это время пошептались. Задача: разработать за них такую стратегию, чтобы при экзекуции гарантированно уцелело как можно большее число гномов (как здесь уже подсказали - 99).

Комментировать
учитель Александр Симин: Всеволод Владимирович, спасибо! // 18 сентября 2007, 17:51

Комментировать
учитель Сергей Чистович: А вот ещё задача // 12 сентября 2007, 20:27

Есть большая группа людей - числом, положим, Эн Большое. Каждый может знать или не знать каждого другого, причём отношение это не симметричное (если я знаю Дарью Дическул, она может меня и не знать :) ). Эти отношения записаны в матрицу NxN, ноликами и единичками.

Будем считать знаменитостью человека, которого знают все, а сам он не знает никого. Вопрос: можно ли за O(N) (то есть за N*какую-то_константу) операций выяснить, есть ли у нас в обществе знаменитость?

Комментировать
учитель Александр Симин: по-моему можно... // 14 сентября 2007, 12:46

хотя я и не очень уверен, что правильно - можно поочередно убирать из матрицы j-ую строку и j-ый столбец (как называется эта операция??? :-)) и считать сумму по оставшимся строкам/столбцам. В зависимости от того, поменялась ли сумма на N (все знают человека j) или не поменялась (человек j не знает никого) - и определяется, есть ли знаменитость.
Примерно так.

Комментировать
учитель Сергей Чистович: Я не совсем понял, что ты предлагаешь, // 14 сентября 2007, 13:26

Но такое впечатление, что количество операций будет примерно N^3, нет? Сумму считать - это тебе не фунт изюму...

Понятно, что за 2N^2 сделать не проблема: пройтись по всей матрицен вдоль и поперек, да поискать ряд, где все единички и строку, где все нули. Но это слишком долго.

Комментировать
учитель Александр Симин: Ну, // 14 сентября 2007, 15:35

я и предлагаю пройтись по всем, например, строчкам и поискать, где все нули. Потом для нулевых строк проверить соответствующие столбцы. Только сумму нужно считать для матрицы без j-й строки и j-го столбца, так как сам себя человек всегда знает... или нет?
Только ты определись с понятием "операция", так как для меня "поискать ряд, где все единички и строку, где все нули" - это непонятно. А сумма элементов любой строки/столбца - это имхо операция, нет? Кроме того, даже сама сумма не нужна, нужно сравнить больше она, равна или меньше нуля или N.

Комментировать
учитель Сергей Чистович: Ты программист или что? // 14 сентября 2007, 17:22

Найти сумму N чисел - это N операций. Ладно, N-1. Проверить N чисел, являются ли они нулём - тоже N. Не очевидно?

Комментировать
учитель Александр Симин: упаси Боже... // 14 сентября 2007, 17:26

неочевидно. Ладно, не буду мешать.

Комментировать
: Я решил! // 15 сентября 2007, 01:08

Спасибо, Вам, Сережа, за интересную задачу! Она мне показалась свежей (хотя похожа на вступительные испытания для программистов).
Сегодня я ее решил. Правильный ответ: можно!
Если Вам интересно, могу опубликовать алгоритм.

Комментировать
учитель Сергей Чистович: Я думаю, пока сохраним его в тайне :) // 17 сентября 2007, 11:46

Я тоже решил, мне не нвдо.
Вроде кого-то на собеседовании в гугль спрашивали.

Комментировать
учитель Дмитрий Кобак: Я тоже решил! // 17 сентября 2007, 22:13

Задача отличная. Я её наконец решил, сидя вчера в поезде Франкфурт-Фрайбург.

Комментировать
учитель Сергей Чистович: нас уже трое! // 18 сентября 2007, 13:22

Два преподавателя, два выпускника. Всего трое. Ещё бы хоть одного действующего гимназиста...

Комментировать

«Кто занимается философией греков, на каждом шагу наталкивается на эту способность ставить принципиальные вопросы, и, следовательно, читая греков, он упражняется в умении владеть одним из наиболее мощных интеллектуальных орудий, выработанных западноевропейской мыслью»

В. Гейзенберг,
немецкий физик, один из основателей квантовой механики