сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

В пер­вен­стве по фут­бо­лу участ­ву­ет 20 ко­манд, ко­то­рые иг­ра­ют по разу друг с дру­гом. Какое наи­мень­шее число игр долж­но быть сыг­ра­но, чтобы среди любых трех ко­манд на­шлись две, уже сыг­рав­шие между собой?

Спрятать решение

Ре­ше­ние.

Будем рас­смат­ри­вать не­сыг­ран­ные игры. Усло­вие озна­ча­ет, что не­сыг­ран­ные игры не об­ра­зу­ют тре­уголь­ни­ков. До­ка­жем ин­дук­ци­ей по k, что для 2k ко­манд наи­боль­шее число не­сыг­ран­ных игр не боль­ше k в квад­ра­те .

База ин­дук­ции: k=1 (оцен­ка оче­вид­на).

Шаг ин­дук­ции: Пусть до­ка­за­но для k: до­ка­жем для k плюс 1. Если не­сыг­ран­ных игр нет, то всё до­ка­за­но. Иначе вы­де­лим про­из­воль­ные ко­ман­ды A и B, не иг­рав­шие между собой. За­ме­тим, что не­сыг­ран­ных игр с уча­сти­ем ко­манд A или B не более 2 k (не счи­тая игры между A и B), так как для любой ко­ман­ды C сыг­ра­на хотя бы одна из игр AC и BC. Те­перь рас­смот­рим все ко­ман­ды, кроме A и B и при­ме­ним пред­по­ло­же­ние ин­дук­ции  — среди них не сыг­ра­но не более k в квад­ра­те игр. От­сю­да общее ко­ли­че­ство не­сыг­ран­ных игр не более k в квад­ра­те плюс левая круг­лая скоб­ка 2 k плюс 1 пра­вая круг­лая скоб­ка = левая круг­лая скоб­ка k плюс 1 пра­вая круг­лая скоб­ка в квад­ра­те , что и тре­бо­ва­лось до­ка­зать.

Под­став­ляя k=10 по­лу­ча­ем, что число не­сыг­ран­ных игр не более 100, а число всех воз­мож­ных игр  дробь: чис­ли­тель: 20 умно­жить на 19, зна­ме­на­тель: 2 конец дроби =190, от­ку­да число сыг­ран­ных игр не менее 190 минус 100=90.

Оцен­ка до­сти­га­ет­ся, если раз­бить ко­ман­ды на две рав­ные груп­пы, в каж­дой из ко­то­рых про­ве­сти все матчи, а между груп­па­ми не про­во­дить ни од­но­го.

 

Ответ: 90 игр.

Спрятать критерии
Критерии проверки:

Общие кри­те­рии оце­ни­ва­ния

По ре­зуль­та­там про­вер­ки каж­до­го за­да­ния вы­став­ля­ет­ся одна из сле­ду­ю­щих оце­нок:

а) «+», «±» — за­да­ча ско­рее ре­ше­на;

б) «∓», «−» — за­да­ча ско­рее не ре­ше­на;

в) за за­да­чу, к ре­ше­нию ко­то­рой участ­ник не при­сту­пал, ста­вит­ся оцен­ка «0».

При под­ве­де­нии ито­гов учи­ты­ва­ет­ся толь­ко ко­ли­че­ство в целом ре­шен­ных задач - задач, за ко­то­рые по­став­ле­на оцен­ка «+» или «±».

Оцен­ки по за­да­чам име­ют­ся в таб­ли­це в лич­ном ка­би­не­те участ­ни­ка. Оцен­ки внут­ри ра­бо­ты и на ти­туль­ном листе ра­бо­ты вы­став­ле­ны в про­цес­се пред­ва­ри­тель­ной про­вер­ки и не яв­ля­ют­ся ос­но­ва­ни­ем для апел­ля­ции.

При­ведённые далее кри­те­рии опи­сы­ва­ют оцен­ки про­дви­же­ний и оши­бок, встре­ча­ю­щих­ся во мно­гих ра­бо­тах. По­это­му они не под­ле­жат из­ме­не­нию и могут быть ис­поль­зо­ва­ны для апел­ля­ции толь­ко в слу­чае, если вы ука­же­те, что какое-то место в вашей ра­бо­те, под­хо­дя­щее под один из этих кри­те­ри­ев, оце­не­но не в со­от­вет­ствии с ним.

Ком­мен­та­рий по оце­ни­ва­нию дан­ной за­да­чи

При­ве­ден при­мер схемы тур­ни­ра, при ко­то­рой до­сти­га­ет­ся вер­ный ответ, но до­ка­за­тель­ство того, что мень­ше игр быть не могло, от­сут­ству­ет или не­пол­но — «∓».

По­лу­чен не­вер­ный ответ (за ис­клю­че­ни­ем ариф­ме­ти­че­ских оши­бок) — «−».