В декабре, у нас на работе, с интервалом в 1-3 дня выпадают 4 дня рождения сотрудников (коллектив небольшой, меньше 25 человек). Хотя совпадения в один день нет, я все же вспомнил про парадокс дней рождения и предложил коллегам условие этой задачи из теории вероятностей. К моему удивлению никто из них про эту задачу не слышал и многие принялись доказывать мне, что я не прав. Поэтому, я решил рассказать про этот парадокс (хотя в строгом смысле парадокса нет) в этом блоге:

В группе из 23-х и более человек вероятность того, что дни рождения совпадут хотя бы у двух из них, выше 50%.

За доказательством я отправляю вас в Википедию. Там все очень хорошо расписано.

Про этот парадокс я впервые прочитал в замечательной книге Рэймонда Смаллиана "Принцесса или тигр?" когда учился в школе. Он там упоминался вскользь, в одной из задач:

Как плохо быть рассеянным. Следующая история произошла на самом деле.
   Как хорошо известно, с вероятностью более 50% можно утверждать, что в группе, состоящей как минимум из 23 человек, всегда найдутся по крайней мере двое, у которых день рождения падает на одно и то же число. В свое время я преподавал математику в Принстонском университете и как-то занимался со студентами элементарной теорией вероятностей. Я объяснил своим слушателям, что если число людей в группе увеличить с 23 до 30, то вероятность того, что в ней окажутся по крайней мере двое, которые родились в один и тот же день, окажется близка к единице.
- Но, - продолжал я, - поскольку вас здесь всего 19, то вероятность того, что у двоих из вас дни рождения совпадают, будет гораздо меньше 50%.
Тут один из студентов поднял руку:
- Бьюсь об заклад, профессор, что по крайней мере у двоих из присутствующих здесь дни рождения должны совпасть.
- С моей стороны было бы не очень честно принимать ваше пари, - ответил я. - Ведь теория вероятностей целиком на моей стороне.
- Это не имеет значения, - упорствовал студент. - Я все-таки готов с вами поспорить!
- Ну, ладно, - согласился я, надеясь преподать юному скептику достойный урок. Затем я стал по очереди опрашивать студентов, с тем чтобы каждый назвал дату своего рождения. Не успели мы выслушать и половину присутствующих, как вдруг вся аудитория, в том числе и я, покатились со смеху по поводу моей бестолковости.
   Юноша, который так самоуверенно вступил со мной в спор, не знал даты рождения никого из присутствующих, за исключением, конечно, самого себя. Не догадаетесь ли вы, почему он был так уверен в своей правоте?

Ответ смотрите в комментариях.

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

Если у кого не хватит терпения, то ответы здесь.

Хочу поблагодарить читателя Ravlyk, оставившего совершенно правильный ответ на пятую задачу в комментариях:

5. На клетчатом поле 8х8 вырезали по клетке в противопол-х углах диагонали.. Можно ли замостить получившееся поле паркетинами 2х1? Ответ доказать.

Ответ: Нет.

Доказательство:

Пусть поле будет шахматное, с черными и белыми клетками.  Вырезано было 2 клетки одинакового цвета (на одной диагонили все клетки одного цвета). Как результат клеток одного из цветов больше чем клеток другого цвета. Каждая паркетина 2х1 ложится на две соседние клетки, причем очевидно - это клетки разных цветов. Соответственно в самом лучшем раскладе останутся две клетки одного цвета, на которые невозможно будет уложить паркетину.

Спасибо!

Что-то я затянул с ответами на вопросы с собеседования в ABBYY. Да и вообще, давно ничего не писал в блоге. Надо срочно исправляться.

Сегодня рассмотрим вторую задачу:

2. Дан массив a[1],..a[N].. найти m,k (m<k) такие что a[m] + ..+a[k] — максимальна. Сложность алг-ма = N.

Вообще-то, не зная заранее решения, найти алгоритм, работающий за время O(N), в течение короткого времени (на собеседовании) довольно сложно. Те же, кто это действительно могут, работают не в ABBYY. Гораздо более полезное собеседование можно провести, убрав требование быстродействия O(N). Нетрудно написать алгоритм работающий со скоростью O(N³). Далее, легко его оптимизировать до O(N²). На этом этапе можно многое узнать о сообразительности кандидата. Используя подсказки, можно прийти к алгоритму O(N log N). Лично я именно так проводил бы собеседование, основанное на этой задаче.

Что касается решения O(N), то оно, наряду с другими вариантами, прекрасно описано в книге Джона Бентли "Жемчужины программирования" (глава 7). Этой замечательной книги, к сожалению, сейчас нет в продаже. Найти ее можно только в электронном виде (http://librus.ru/down.php?book=05753).

Приведу реализацию алгоритма из книги на C#:

	

		

			
            int[] a = { 1, 2, -2, 3, -5, 1, 1, 3};
		
		

			
            int N = a.Length;
		
		

			
 
		
		

			
            int maxSoFar = 0;
		
		

			
            int maxEndingHere = 0;
		
		

			
 
		
		

			
            for(int i = 0; i < N; i++)
		
		

			
            {
		
		

			
                maxEndingHere = Math.Max(maxEndingHere + a[i], 0);
		
		

			
                maxSoFar = Math.Max(maxSoFar, maxEndingHere);
		
		

			
            }
		
	

В этом примере вычисляется только максимальная сумма, без определения индексов m,k.  Заменив методы Max на конструкции if ... else с запоминанием индексов, несложно найти m и k.

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

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

Пусть красный цвет соответствует 0, а белый - 1. Тогда, чиновник, который отвечает первым и видит цвета всех остальных, подсчитывает сумму по модулю 2 и называет получившийся цвет. С вероятностью 50% результат совпадет с его цветом. Далее, следующий чиновник, подсчитав сумму по модулю 2 всех, кто стоит перед ним, и зная ответ предыдущего, стопроцентно правильно называет свой цвет. И так по цепочке. Таким образом, действуя по этому алгоритму, стопроцентно выживут все, кроме первого (его вероятность выжить 50%).

Как и обещал, привожу ответ на первую задачу.

1. Царь построил своих чиновников в колонну (лицом к затылку следующего), надел по колпаку одного из цветов — красного или белого.. и сказал поочереди назвать цвет своего колпака. Кто не угадает — смерть. Первый отвечал тот кто видит всех и т.д. попорядку.. Вопрос: о чем должны договориться чиновники чтобы минимизировать кол-во смертей.

Исходим из предположения, что колпаки одеты случайным образом, а колонна достаточно длинная.

Очевидно, что если чиновники будут пытаться угадать свой цвет, то по теории вероятности половина из них не выживет. Чтобы увеличить вероятность правильного ответа каждый чиновник должен своим ответом передать информацию другим (т.к. он видит цвет всех колпаков).

Если каждый нечетный по счету чиновник (1-й, 3-й, 5-й и т.д.) будет называть цвет колпака, находящегося перед ним, а каждый четный повторять названный цвет, то выживут все четные чиновники и половина нечетных. Это становится легко понятным если расписать возможные комбинации пар (Б - белый, К - красный):

БК - 1-й убит
ББ - 1-й жив
КК - 1-й жив
КБ - 1-й убит

Т.е. выживут 75% чиновников.

На форуме RSDN человек делится неудачным опытом собеседования в ABBYY - не смог справиться с тестовыми заданиями. Вот что его спросили:

1. Царь построил своих чиновников в колонну (лицом к затылку следующего), надел по колпаку одного из цветов — красного или белого.. и сказал поочереди назвать цвет своего колпака. Кто не угадает — смерть. Первый отвечал тот кто видит всех и т.д. попорядку.. Вопрос: о чем должны договорится чиновники чтоб минимизировать кол-во смертей.
2. Дан массив a[1],..a[N].. найти m,k (m<k) такие что a[m] + ..+a[k] — максимальна. Сложность алг-ма = N.
3. Алгоритм вычисления a^N (N- целое) за log N шагов без выделения доп. памяти.
4. На турляндском языке дан перевод чисел:
23: апвып пвадлор вапр (пишу примерно)
334: пвап по пвадалл
.. (не помню)
Переведите 35, 343..
И в качестве контрольного выстрела еще дали задачу:
5. На клетчатом поле 8х8 вырезали по клетке в противопол-х углах диагонали.. Можно ли замостить получившееся поле паркетинами 2х1? Ответ доказать.

Ответы смотрите через пару дней. Постарайтесь решить сами. Задача номер 1 требует только логического мышления.

Принцесса или тигр?

   У Фрэнка Стоктона есть сказка, которая называется "Принцесса или тигр?" В этой сказке один узник должен угадать, в какой из двух комнат находится принцесса, а в какой - тигр. Если он укажет на первую комнату, то женится на принцессе, если на вторую, то его (вполне возможно) растерзает тигр.

   В некотором царстве правил король. Однажды он тоже прочитал эту сказку.
-  В самый раз для моих заключенных! - сказал он своему министру. - Только я не хочу полагаться на случайности. Пусть на дверях каждой комнаты повесят по табличке, а заключенному будет кое-что сказано о них. Если узник не дурак и способен рассуждать логически, он сумеет сохранить себе жизнь и в придачу заполучить прелестную невесту.
-  Блестящая идея, ваше величество! - согласился министр.

Испытания первого дня

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

1. Первое испытание.

- А что, если в обеих комнатах сидят тигры? - спросил узник. - Что же мне тогда-то делать?
- Считай, не повезло, - ответил король.
- А если в обеих комнатах окажется по красавице? - поинтересовался узник.
- Считай, подфартило, - сказал король. - Уж это ты и сам бы мог сообразить!
- Ну, хорошо, а если в одной комнате принцесса, а в другую посадили тигра, что тогда? - не успокаивался узник.
- Вот тут-то уже все зависит от тебя! Не так ли?
- Да откуда же мне знать, где кто? - сокрушенно вздохнул узник.
   Тут король указал на таблички, прикрепленные к дверям каждой из комнат. На них было написано:

- А это правда, что здесь написано? - спросил узник.
- На одной - правда, - отвечал король, - на другой - нет.
   А вы на месте узника, какую бы дверь открыли? (Конечно, если вы предпочитаете принцессу тигру.)

2. Второе испытание.

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

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

3. Третье испытание.

   Во время этого испытания король объявил, что опять утверждения на обеих табличках одновременно либо истинны, либо ложны. Надписи же были вот какие:

   Кто же обнаружится в первой комнате - принцесса или тигр? А во второй?

Ответы смотрите в комментариях.

В предыдущей версии блога я уже писал про прикольный логический тест.

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

Сегодня знакомый был на собеседовании в одной уважаемой (и уважающей себя) компании.
Получил на руки вот такой вот тест на логическое мышление, надо было ответить на 12 вопросов.
Я так понял, главная идея теста проверить человека на стрессоустойчивость, потому что знакомому очень хотелось встать, порвать листочки, дать в лицо hr-щику, поклониться и уйти. Я сам ответил верно на все вопросы, но меня, скорее всего спасло то, что, среди прочего, я по диплому имею право преподавать логику в учебных заведениях.
Мне объяснили так, если человек отвечает правильно на все 12 вопросов - это шоколад, а не сотрудник.
Меньше 6 - у этого человека вообще туго с логикой.

Внимание:

Тест на логическое мышление. Используйте только ту информацию, которая имеется в тексте вопроса, не полагайтесь на свой жизненный опыт.

1. Некоторые улитки являются горами. Все горы любят кошек.
Значит, все улитки любят кошек.
а) правильно
б) неправильно

2. Все крокодилы умеют летать. Все великаны являются крокодилами.
Значит, все великаны могут летать.
а) правильно
б) неправильно

3. Некоторые головки капусты - паровозы. Некоторые паровозы играют на рояле.
Значит, некоторые головки капусты играют на рояле.
a) правильно
б) неправильно

4. Две поляны никогда не похожи одна на другую. Сосны и ели выглядят совершенно одинаково.
Значит, сосны и ели не являются двумя полянами.
а) правильно
б) неправильно

5. Никто из людей не может стать президентом, если у него красный нос. У всех людей нос красный.
Значит, никто из людей не может стать президентом.
а) правильно
б) неправильно

6. Все вороны собирают картины. Некоторые собиратели картин сидят в птичьей клетке.
Значит, некоторые вороны сидят в птичьей клетке.
a) правильно
б) неправильно

7. Только плохие люди обманывают или крадут. Катя - хорошая.
а) Катя обманывает
б) Катя крадет
в) Катя не крадет
г) Катя обманывает и крадет
д) ни одно из вышеперечисленных

8. Все воробьи не умеют летать. У всех воробьев есть ноги.
а) без ног воробьи не могут летать
б) некоторые воробьи не имеют ног
в) все воробьи, у которых есть ноги, не могут летать
г) воробьи не могут летать, потому что у них есть ноги
д) воробьи не могут летать и у них нет ног
е) ни одно из вышеперечисленных

9. Некоторые люди - европейцы. Европейцы имеют три ноги.
а) люди с двумя ногами не являются европейцами
б) европейцы, которые являются людьми, иногда имеют три ноги
в) европейцы с двумя ногами иногда являются людьми
г)Людей не европейцев, с тремя ногами не бывает
д)Люди имеют три ноги потому что они европейцы
е)ни одно из вышеперечисленных

10. Цветы - это зеленые звери. Цветы пьют водку.
а) все зеленые звери пьют водку
б) все зеленые звери являются цветами
в) некоторые зеленые звери пьют водку
г) Зеленые звери не пьют водку
д) зеленые звери не являются цветами
е)ни одно из вышеперечисленных

11. Каждый квадрат круглый. Все квадраты красные.
а) бывают квадраты с красными углами
б) бывают квадраты с круглыми углами
в) бывают круглые красные углы
г) углы и квадраты - круглые и красные
д) ни одно из вышеперечисленных

12. Хорошие начальники падают с неба. Плохие начальники могут петь.
а) Плохие начальники летят с неба вниз.
б) Хорошие начальники, которые умеют летать - могут петь.
в) некоторые плохие начальники не могут петь.
г) некоторые хорошие начальники -плохие, так как они умеют петь.
д) ни одно из вышеперечисленных

Ответы смотрите в комментариях.