|
На экзамене по английскому десяти школьникам был предложен тест, состоящий из нескольких вопросов. Известно, что любые шесть школьников ответили вместе на все вопросы (то есть на каждый вопрос хоть один из них дал правильный ответ), а любые пять — нет. При каком минимальном количестве вопросов это могло быть? задан 11 Дек '12 17:58 
ilia |
|
Возьмем произвольную пятерку школьников. Они все не ответили на некоторый вопрос, общий для всех. Причем каждый из остальных ответ на этот вопрос знает (при добавлении этого каждого к пятерке "знания" становятся полными). Значит, для каждого подмножества из 5 человек есть по крайне мере один общий вопрос и для всех пятерок эти вопросы разные. Таким образом, нам нужно не менее $%C_{10}^5 = 252$% вопросов. Довольно утомительный экзамен! отвечен 11 Дек '12 18:40 
DocentI По идее надо еще подтвердить, что подобное распределение знаний возможно. Но это легко сделать, используя идею доказательства. А именно, пронумеруем все пятерки и будем считать, что каждый знает все вопросы с номерами тех пятерок, куда он входит (т.е. это пятерки "знающих")
(12 Дек '12 17:14)
DocentI
|
Такое ощущение, что это уже было, не помню точно вопрос...