(no subject)

[leblon]

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

Comments

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

[clovis3.livejournal.com]

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

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

[leblon.livejournal.com]

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