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

Форум

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

выпускник Юрий Мельников: Важный (!) Вопрос (?) // 12 сентября 2007, 00:47

Дарья, как бы вы поступили, если бы Вас имплицировал Михаил Федоровский вафельницей, и причем тут сто (100) гномиков?

Комментировать
выпускник Юрий Мельников: 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

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

Комментировать
учительница В. Б. Гефтер (Жижина): я не датчанин... (с) // 12 сентября 2007, 20:53

раз уж гномиков почти всех спасли, нельзя ли узнать поподробнее о вафельнице?

Комментировать
: [без темы] // 15 сентября 2007, 01:02

Да-да! Начало этой серии непонятно для непосвященных! Какая Дарья? Какая вафельница??? Это больно, когда "имплицируют"?

Комментировать
Лилия Гильфанутдинова: Я про гномов не поняла... // 18 сентября 2007, 16:16

Я ничего не поняла про гномов... Почему 99?!!

Комментировать
учитель В. В. Зельченко: [без темы] // 19 сентября 2007, 19:38

На этот вопрос и нужно ответить. Вернее, не "почему", а "как".

Комментировать
выпускник Илья Нахмансон: Загадка Иванишевича // 19 сентября 2007, 04:37

Ну что вы тут оторванные от реальности конструкты обсуждаете, гномы какие-то, знаменитости. По правде говоря, для работы в гугле ничего этого не нужно :)
Если устраивать викторину - а пуркуа бы и не па? - то математикам математиково, а и о насущном забывать нельзя, есть знания, без которых жизнь не имеет никакого смысла. Такой, например, вопрос: Горан Иванишевич, один из самых ярких теннисистов 90-ых, добивался прекрасных результатов, хотя игра его была нестабильна как по ходу турнира, так и на разных отрезках отдельных матчей. Сам он объяснял это растроением личности, говоря, что в нем уживаются три Горана: good & gracious Goran: bad & crazy Goran и... Каким был третий Горан? Если у вас нет ответа на этот вопрос, то вы точно не Иванишевич.

Комментировать
выпускница Дина Гидон: [без темы] // 21 сентября 2007, 14:33

911?

Комментировать
выпускник Илья Нахмансон: bingo! // 21 сентября 2007, 20:44

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

«Легкая школа — это социальное преступление»

Ф. Ф. Зелинский,
крупнейший русский филолог-классик