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

[Гост]

Група от 15 депутати използва услугите на 5 секретарки. За всеки депутат е определена точно една и ниоя не работи за повече от 4 депутати. Докажете, че поне 3 секретарки работят за 3 или повече депутати.

[Knowledge Greedy]

Група от 15 депутати използва услугите на 5 секретарки. За всеки депутат е определена точно една и никоя не работи за повече от 4 депутати. Докажете, че поне 3 секретарки работят за 3 или повече депутати.

сл. 1.) При три секретарки, работещи за по 4 депутати - въпросът е решен (оставащите трима депутати имат две секретарки).

сл. 2.) Ако две секретарки (А и В) работят за по 4 -ма депутати, остават три, които ще трябва да работят за 7 депутати. Следователно една от тези три ще работи за трима, и заедно с А и В изпълняват условието на задачата.

сл. 3.) Ако само една секретарка работи за 4 -ма депутати, остават четири, които ще трябва да работят за 11 депутати. Тъй като подминахме случай 2), сред тези четири ще има три, всяка от които работи за по трима депутати.

сл. 4.) Ако няма секретарка работеща за 4 -ма депутати, всичките 5 ще трябва да работят за 15 депутати. И за да е изпълнено условието, всяка от тях работи за трима депутати.