Комбинаторна задача 3

[Гост]

Семейство (мъж и жена) Иванови поканили в своя дом 4 приятелски семейства (съставени също от мъж и жена). Те пристигнали заедно и се събрали всички приятели на входа. Здрависали се, като всеки се е здрависал с някого най-много един път и никой не се е здрависал със своя партньор. На госпожа Иванова и станало любопитно всеки с колко души се е здрависал. Попитала всеки по отделно. За нейна изненада получила само различни отговори.
С колко души се е здрависала госпожа Иванова?

[peyo]

Семейство (мъж и жена) Иванови поканили в своя дом 4 приятелски семейства (съставени също от мъж и жена). Те пристигнали заедно и се събрали всички приятели на входа. Здрависали се, като всеки се е здрависал с някого най-много един път и никой не се е здрависал със своя партньор. На госпожа Иванова и станало любопитно всеки с колко души се е здрависал. Попитала всеки по отделно. За нейна изненада получила само различни отговори.
С колко души се е здрависала госпожа Иванова?

Учидващо трудна задача!

Ако се опитаме да тестваме всички комбинации ще трябва да направим $2^{40} =$ около 1 трилион теста, което не е добре.

Затова ще подходим по друг начин. Първо ще решим задачата ако на гости са дошли само една двойка, после две двойки и ще се надяваме, че ще намерим закономерност.

Ако са дошли само семейство А, то решение е г-н А се здрависва с г-н и г-жа Иванови, а г-жа А не се здрависва. Тогава имаме 0,1 и 2 здрависвания и г-жа Иванова има 1 здрависване.

Ако веднага след тях са дошли семейство Б, то г-н Б се здрависва с всички които вече са дошли, а г-жа Б не се здрависва. Тогава имаме 0, 4,1,3,2 здрависвания и г-жа Иванова има 2 здрависвания.

По същия начин всяко следващо семейство г-н Х ще се здрависа с всички вече пристигнали, а г-жа Х няма да се здрависва с никого.

Така стигаме до момента когато имаме гости 4 двойки и тогава г-жа Иванова ще се е здрависала 4 пъти с което задачата е решена.

Така не само намерихме отговора на задачата но намерихме и алгоритъм по-който може да станат здрависванията.

gzhaIvanova.png (35.45 KiB) Прегледано 1200 пъти

Останаха няколко въпроса неизяснени:

1. Съществува ли друг алгоритъм и този друг алгоритъм ще има ли друг отговор на задачата? Тук не разглеждаме случая когато само г-жата се здрависва а г-на не, защото е симетричен.

2. Може ли да намерим отговора без да намерим алгоритъм?