(no subject)

[leblon]

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

Comments

[mancunian.livejournal.com]

Зависит от того, сколько там было русских.

Кто дал задачу?

[clovis3.livejournal.com]

Она пожала 9 рук. Доказательство по индукции. Количество возможных рукопожатий -- от 0 до 18. 19 человек сделали разное число рукопожатий, поэтому каждое возможное число рукопожатий реализовано один раз. Жена математика не может сделать 18 рукопожатий, иначе ни у кого не будет 0. Поэтому 18 рукопожатий совершает кто-то другой. Тогда 0 рукопожатий должен совершить его партнёр (ведь все прочие сделали хотя бы одно рукопожатие с этим человеком). Если убрать пару (18,0), то задача сведётся к 9-ти парам (опять у всех будет разное число), и количество рукопожатий у каждого уменьшилось на 1.

Re: Кто дал задачу?

[leblon.livejournal.com]

Услышал от Мартина Рочека. Не знаю, от кого он услышал.

[avva.livejournal.com]

девять. Красивая задачка для решения в уме.

[relf.livejournal.com]

Слышал эту задачку лет 5 назад на тусовке в Сан-Диего.

[jedal]

...А 8 лет назад она была напечатана в Кванте.

[shuffle81.livejournal.com]

С несколько сомнительной предысторией, впрочем, - по моим воспоминаниям (только что подтверждённым моим е-майл архивов), предложена на собеседовании она была весной 2001 года, а предложил для собеседования её a_shen. Обсуждение задачи с неким преподавателем ВУЗа тоже было, но скорее в жанре уговорить этого преподавателя привести его дочку на собеседования, продемонстрировав, какие классные у нас задачи (и это обсуждение вёл лично я) :-)

Трудно ожидать

[jedal]

от байки абсолютной истинности, мне кажется.

(На самом деле, у меня было воспоминание, что я видел эту задачу то ли в твоей, то ли в Шеневской книжке, но с ходу не нашел, так что ограничился ссылкой на Квант.)

Re: Трудно ожидать

[shuffle81.livejournal.com]

самый низ стр.33: собеседование 18 апреля 2001 года, задача 5 (http://www.maths.tcd.ie/~vdots/all2.pdf) :)

[yigal_s]

В конце 1998 года я эту задачку получил на интервью.