На экзамене по английскому десяти школьникам был предложен тест, состоящий из нескольких вопросов. Известно, что любые шесть школьников ответили вместе на все вопросы (то есть на каждый вопрос хоть один из них дал правильный ответ), а любые пять — нет. При каком минимальном количестве вопросов это могло быть?

задан 11 Дек '12 17:58

изменен 11 Дек '12 19:19

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

Такое ощущение, что это уже было, не помню точно вопрос...

(11 Дек '12 18:34) DocentI
10|600 символов нужно символов осталось
4

Возьмем произвольную пятерку школьников. Они все не ответили на некоторый вопрос, общий для всех. Причем каждый из остальных ответ на этот вопрос знает (при добавлении этого каждого к пятерке "знания" становятся полными). Значит, для каждого подмножества из 5 человек есть по крайне мере один общий вопрос и для всех пятерок эти вопросы разные. Таким образом, нам нужно не менее $%C_{10}^5 = 252$% вопросов. Довольно утомительный экзамен!

ссылка

отвечен 11 Дек '12 18:40

изменен 11 Дек '12 21:36

По идее надо еще подтвердить, что подобное распределение знаний возможно. Но это легко сделать, используя идею доказательства. А именно, пронумеруем все пятерки и будем считать, что каждый знает все вопросы с номерами тех пятерок, куда он входит (т.е. это пятерки "знающих")

(12 Дек '12 17:14) DocentI
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,396
×717

задан
11 Дек '12 17:58

показан
2014 раз

обновлен
12 Дек '12 17:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru