1.  Сна­ча­ла вы­яс­ним, как могли сыг­рать три ко­ман­ды между собой с со­блю­де­ни­ем усло­вий за­да­чи. Если внут­ри трой­ки не было ни­чьих, един­ствен­ным под­хо­дя­щим ва­ри­ан­том будет (Т1), когда каж­дая про­иг­ра­ла и вы­иг­ра­ла по од­но­му матчу, у всех по 3 очка. Если ничья была ровно одна, то сде­лав­шие её ко­ман­ды либо обе вы­иг­ра­ли у тре­тьей (Т2: 4,4 и 0 очков), либо обе про­иг­ра­ли тре­тьей (Т3: 1,1 и 6 очков). Слу­чай ровно с двумя ни­чьи­ми не­воз­мо­жен. Под­хо­дит и ва­ри­ант с тремя ни­чьи­ми (Т4): все на­би­ра­ют по 2 очка.

2.  Из пунк­та 1 сле­ду­ет, что: а) Если две А и Б ко­ман­ды сыг­ра­ли между собой вни­чью, то ре­зуль­та­ты мат­чей любой дру­гой ко­ман­ды с А и с Б оди­на­ко­вы. б) Если ко­ман­да сыг­ра­ла с ко­ман­да­ми А и Б с оди­на­ко­вым ре­зуль­та­том, то А и Б сыг­ра­ли между собой вни­чью.

3.  До­ка­жем, что в тур­ни­ре была хотя бы одна ничья. В про­тив­ном слу­чае, всего имеем 45 побед во всех мат­чах, зна­чит, найдётся ко­ман­да А, вы­иг­рав­шая не мень­ше 5 мат­чей. Рас­смот­рим ко­ман­ды Б и В, про­иг­рав­шие А, оче­вид­но, что трой­ка А, Б, В не удо­вле­тво­ря­ет усло­вию за­да­чи.

4.  Обо­зна­чим какие-ни­будь ко­ман­ды, сыг­рав­шие между собой вни­чью, за А и Б. В первую под­груп­пу вклю­чим все ко­ман­ды, сыг­рав­шие с А и Б вни­чью, во вто­рую все ко­ман­ды, вы­иг­рав­шие у А и Б, в тре­тью  — все ко­ман­ды, про­иг­рав­шие А и Б. Из пунк­та 2.б) сле­ду­ет, что в пре­де­лах каж­дой под­груп­пы все ко­ман­ды сыг­ра­ли между собой вни­чью.

а)  Пусть за по­бе­ду в матче ко­ман­де на­чис­ля­лось n очков, всего в тур­ни­ре было сыг­ра­но 15 мат­чей, из ко­то­рых x окон­чи­лись по­бе­дой одной из ко­манд, а осталь­ные 15 − x  — вни­чью. В ни­чей­ных мат­чах участ­ни­ки в сумме на­би­ра­ют 2 очка, а в осталь­ных  — n очков, по­это­му всего в тур­ни­ре всеми ко­ман­да­ми было на­бра­но очка, от­ку­да Всего игр было 15, по­это­му x может рав­нять­ся 1, 2 или 11. В пер­вых двух слу­ча­ях n равно 24 или 13, что пре­вос­хо­дит мак­си­маль­ное ко­ли­че­ство очков, на­бран­ных ко­ман­да­ми, чего быть не может, так как по­бе­да в матче ста­но­вит­ся не­воз­мож­ной в прин­ци­пе, зна­чит, все матчи окон­чат­ся вни­чью, что про­ти­во­ре­чит пред­по­ло­же­нию о x. В остав­шем­ся слу­чае x равен 11, тогда n равно 4  — ко­ли­че­ство очков, на­чис­ля­е­мое за по­бе­ду.

б)  Найдём ко­ли­че­ство вы­иг­ры­шей, ни­чьих и про­иг­ры­шей у каж­дой ко­ман­ды. Всего было че­ты­ре ни­чьих и 11 мат­чей, окон­чив­ших­ся по­бе­дой одной из ко­манд. Каж­дая ко­ман­да про­ве­ла по пять игр, по­это­му 6 и более очков нель­зя было на­брать толь­ко за счёт ни­чьих, сле­до­ва­тель­но, ше­стая и пятая ко­ман­ды по разу вы­иг­ра­ли и сде­ла­ли по две и три ни­чьих со­от­вет­ствен­но. Если бы четвёртая ко­ман­да вы­иг­ра­ла не более од­но­го раза, у неё было бы не мень­ше четырёх ни­чьих, всего вме­сте с пятой и ше­стой было бы уже не мень­ше ни­чьих, что боль­ше общих 4. Сле­до­ва­тель­но, четвёртая ко­ман­да два­жды вы­иг­ра­ла и три­жды про­иг­ра­ла. В силу тех же со­об­ра­же­ний у тре­тьей ко­ман­ды две по­бе­ды и одна ничья, у вто­рой  — две по­бе­ды и две ни­чьих. У всех ко­манд, кроме пер­вой, по­лу­ча­ем не мень­ше ни­чьих, что равно их об­ще­му числу. Сле­до­ва­тель­но, у пер­вой ко­ман­ды было три по­бе­ды и два по­ра­же­ния.

в)  При­ведём при­мер со­от­вет­ству­ю­ще­го тур­ни­ра. Пятая ко­ман­да три­жды сыг­ра­ла вни­чью, а упер­вой и четвёртой  — ни­чьих не было. Зна­чит, пятая ко­ман­ды сыг­ра­ла вни­чью с ше­стой, тре­тьей и вто­рой. Кроме этих ни­чьих, остаётся по одной у ше­стой и вто­рой, по­это­му они сыг­ра­ли вни­чью между собой. Всё, ничьи за­кон­чи­лись, и они вос­ста­нав­ли­ва­ют­ся од­но­знач­но. А вот ре­зуль­та­тив­ные матчи од­но­знач­но вос­ста­но­вить нель­зя. Один из при­ме­ров, удо­вле­тво­ря­ю­щих усло­вию, такой: пер­вая ко­ман­да вы­иг­ра­ла у четвёртой, пятой и ше­стой, вто­рая  — у пер­вой и тре­тьей, тре­тья  — у пер­вой и ше­стой, четвёртая  — у вто­рой и тре­тьей, пятая  — у четвёртой, ше­стая  — у четвёртой.

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

Пред­по­ло­жим про­тив­ное, что у каж­дой ко­ман­ды число одер­жан­ных ею побед рав­ня­ет­ся числу мат­чей, сыг­ран­ных ею вни­чью. Найдём сумму S ко­ли­честв всех побед, ни­чьих и по­ра­же­ний всех ко­манд. В этой сумме общее число всех одер­жан­ных побед будет равно об­ще­му числу всех по­ра­же­ний и оба этих ко­ли­че­ства, по пред­по­ло­же­нию, равны об­ще­му числу всех ни­чьих. От­сю­да сле­ду­ет, что S долж­но де­лить­ся на 3, од­на­ко оно равно удво­ен­но­му числу всех сыг­ран­ных мат­чей, то есть 17 · 16  =  272 и не де­лит­ся на 3  — про­ти­во­ре­чие. Сле­до­ва­тель­но, пред­по­ло­же­ние не­вер­но и не могло у каж­дой ко­ман­ды число одер­жан­ных ею побед рав­нять­ся числу мат­чей, сыг­ран­ных ею вни­чью.

Ответ: Нет, не могло.

Пусть число участ­ни­ков тур­ни­ка равно n, а число по­пав­ших в 1-ю груп­пу равно k. Тогда число сыг­ран­ных пар­тий равно:

где m  — мало, от­ку­да:

от­ку­да

Если n = 18, то:

тогда

Итак, наи­боль­шее воз­мож­ное число участ­ни­ков равно 18, груп­пы участ­ни­ков на­счи­ты­ва­ют 4 и 14 че­ло­век, ко­ли­че­ство «меж­груп­по­вых» пар­тий равно 2.

Ответ: 18.

Число маль­чи­ков в каж­дой груп­пе может при­ни­мать зна­че­ния Рас­смот­рим сле­ду­ю­щие ве­ли­чи­ны:   — число групп, в ко­то­рых по k маль­чи­ков и де­во­чек:   — число игр между маль­чи­ка­ми в груп­пе, со­дер­жа­щей ровно k маль­чи­ков;   — число игр между де­воч­ка­ми в груп­пе, со­дер­жа­щей ровно k маль­чи­ков. При этом

За­не­сем эти дан­ные в таб­ли­цу.

Тогда

крат­но 5 и не может быть равно 22 или 23. Далее,

крат­но 5 и не может быть равно 28 или −4.

Ответ: нет.

Пусть тен­ни­сист A про­вел ровно k мат­чей, а все осталь­ные участ­ни­ки  — не менее k мат­чей. Разо­бьем тен­ни­си­стов на две груп­пы: в пер­вой  — сам A и те, с кем он сыг­рал, во вто­рой те, с кем A не играл. Пер­вая груп­па со­дер­жит че­ло­век, и каж­дый из них про­вел не менее k игр. Тогда участ­ни­ки из этой груп­пы про­ве­ли не менее мат­чей (в сумме каж­дая игра учи­ты­ва­ет­ся не более двух раз). Во вто­рую груп­пу вхо­дит че­ло­век. По­сколь­ку ни один из них не играл с A, они все долж­ны были сыг­рать друг с дру­гом, то есть про­ве­сти по край­ней мере мат­чей. По­это­му общее число игр не мень­ше, чем

Таким об­ра­зом, нам не под­хо­дит.

По­ка­жем те­перь, что удо­вле­тво­ря­ет усло­вию за­да­чи. Разо­бьем тен­ни­си­стов на две груп­пы по 8 че­ло­век, и пусть в обеих груп­пах все участ­ни­ки сыг­ра­ют друг с дру­гом. В сумме по­лу­чит­ся ровно 56 мат­чей. Среди любых трех тен­ни­си­стов най­дут­ся двое из одной груп­пы, и, зна­чит, они уже сыг­ра­ли между собой.

Ответ: 56.

На­зо­вем цик­лом такую трой­ку участ­ни­ков, что во встре­чах между собой каж­дый из них одер­жал по одной по­бе­де. До­ка­жем вна­ча­ле, что ни один тен­ни­сист не может вхо­дить более чем в один цикл. До­го­во­рим­ся сим­во­лом от­ме­чать факт по­бе­ды A над B. Пусть на­шел­ся участ­ник C, фи­гу­ри­ру­ю­щий в двух раз­ных цик­лах. Эти циклы могут быть двух типов:

1)  (A, B, C) и (C, D, E). Тогда так как иначе

что не­воз­мож­но. Но в этом слу­чае чего так же быть не может;

2)  (A, B, C) и (B, C, D). Тогда вновь Но в этом слу­чае

что также не­воз­мож­но. Таким об­ра­зом, в два цикла тен­ни­сист C вхо­дить не может.

По до­ка­зан­но­му циклы не пе­ре­се­ка­ют­ся, по­это­му их ко­ли­че­ство не пре­вос­хо­дит При­ве­дем при­мер тур­ни­ра с 11 цик­ла­ми. Разо­бьем 33 участ­ни­ка на груп­пы по 3 че­ло­ве­ка и за­ну­ме­ру­ем эти груп­пы чис­ла­ми от 1 до 11. Пусть каж­дая груп­па об­ра­зу­ет цикл, а во встре­че тен­ни­си­стов, вхо­дя­щих в раз­ные груп­пы, по­беж­да­ет спортс­мен из груп­пы с боль­шим но­ме­ром. На­ко­нец, остав­ши­е­ся два участ­ни­ка по­беж­да­ют всех осталь­ных. Такой тур­нир удо­вле­тво­ря­ет усло­вию за­да­чи и имеет ровно 11 цик­лов.

Ответ: 11.

На­зо­вем цик­лом такую трой­ку участ­ни­ков, что во встре­чах между собой каж­дый из них одер­жал по одной по­бе­де. Обо­зна­чим через x общее ко­ли­че­ство цик­лов, а через y  — ко­ли­че­ство всех троек, не об­ра­зу­ю­щих цикла. Тогда   — общее число раз­лич­ных троек участ­ни­ков, от­ку­да

Рас­смот­рим те­перь упо­ря­до­чен­ные трой­ки участ­ни­ков (A, B, C), в ко­то­рых A по­бе­дил B, а B вы­иг­рал у C. Если тен­ни­си­сты A, B, C не об­ра­зу­ют цикла, их можно упо­ря­до­чить од­но­знач­но, а если об­ра­зу­ют  — тремя спо­со­ба­ми (под­хо­дят также цик­ли­че­ские пе­ре­ста­нов­ки трой­ки). Зна­чит, общее число упо­ря­до­чен­ных троек равно С дру­гой сто­ро­ны, для каж­до­го тен­ни­си­ста B его парт­не­ров по трой­ке A и C можно вы­брать не­за­ви­си­мо две­на­дца­тью спо­со­ба­ми, по­сколь­ку B по­тер­пел 12 по­ра­же­ний и одер­жал 12 побед. По­это­му всего есть упо­ря­до­чен­ных троек, от­ку­да Таким об­ра­зом,

Ответ: 650.

При­ве­дем дру­гое ре­ше­ние. Пусть в тур­ни­ре участ­во­ва­ло тен­ни­си­стов, и каж­дый одер­жал по k побед. На­зо­вем цик­лом такую трой­ку участ­ни­ков, что во встре­чах между собой каж­дый из них одер­жал по одной по­бе­де. Обо­зна­чим через S_k общее ко­ли­че­ство цик­лов в тур­ни­ре с участ­ни­ка­ми. Ясно, что До­ба­вим в тур­нир с участ­ни­ка­ми двух новых тен­ни­си­стов A и B и по­смот­рим, на сколь­ко уве­ли­чит­ся число цик­лов. Пусть A вы­иг­рал у B. Тогда осталь­ные участ­ни­ков разо­бьют­ся на груп­пы из и k че­ло­век: пер­вая груп­па про­иг­ра­ла A и вы­иг­ра­ла у B, вто­рая на­о­бо­рот.

Новые циклы могут быть двух типов:

1)  (A, C, D) или (B, C, D), где C, D от­лич­ны от A и B. Если C и D вхо­дят в одну груп­пу, то таких цик­лов быть не может, по­сколь­ку и A и и B либо вы­иг­ра­ли у C и D, либо про­иг­ра­ли им. Пусть C взят из пер­вой груп­пы, а D  — из вто­рой. Если C вы­иг­рал у D, то (A, C, D) об­ра­зу­ет цикл, а (B, C, D)  — нет. Если же D вы­иг­рал у C, то (B, C, D) об­ра­зу­ет цикл, а (A, C, D)  — нет. Таким об­ра­зом, пара (C, D) дает ровно один новый цикл, а общее число цик­лов пер­во­го типа равно

2)  (A, B, C), где C от­ли­чен от A и B. Такая трой­ка будет цик­лом тогда и толь­ко тогда, когда C бе­рет­ся из вто­рой груп­пы. Зна­чит, мы по­лу­ча­ем еще k новых цик­лов.

Из 1) и 2) вы­те­ка­ет, что

от­ку­да для лю­бо­го на­ту­раль­но­го n

Оста­лось под­ста­вить

Пусть для про­сто­ты рей­тин­ги тен­ни­си­стов равны Одна рас­ста­нов­ка оче­вид­на  — по убы­ва­нию рей­тин­га. В дру­гих рас­ста­нов­ках убы­ва­ние на­ру­ша­ет­ся. Это может про­ис­хо­дить толь­ко из-за при­сут­ствия пар со­се­дей и (какой-то одной или обеих). Рас­смот­рим три слу­чая.

1)  Bстре­ча­ет­ся толь­ко пара До и после этой пары может быть любое ко­ли­че­ство тен­ни­си­стов, но их по­ря­док фик­си­ро­ван. При­пи­шем спортс­ме­ну ин­декс 0, если он стоит слева от пары, и 1, если спра­ва. Для каж­до­го из остав­ших­ся тен­ни­си­стов до­пу­сти­мы оба ин­дек­са, по­это­му всего будет рас­ста­но­вок.

2)  Bстре­ча­ет­ся толь­ко пара По­сколь­ку пары и (1, 2) не­до­пу­сти­мы, тен­ни­сист с рей­тин­гом n дол­жен сто­ять пер­вым в ряду, а тен­ни­сист с рей­тин­гом 1  — по­след­ним. Осталь­ные спортс­ме­на могут сто­ять как до пары так и после нее, но в фик­си­ро­ван­ном по­ряд­ке. Таких рас­ста­но­вок всего

3)  Встре­ча­ют­ся пары и Любой из осталь­ных тен­ни­си­стов может рас­по­ла­гать­ся до пер­вой пары, между па­ра­ми и после вто­рой пары. Таких рас­ста­но­вок всего По­сколь­ку пары и могут идти в любом по­ряд­ке, мы по­лу­ча­ем ва­ри­ан­тов.

Таким об­ра­зом, всего воз­мож­но

рас­ста­но­вок.

Ответ:

До­ка­жем вна­ча­ле лемму: в про­из­воль­ном тур­ни­ре тен­ни­сист X, одер­жав­ший наи­боль­шее число побед, круче всех. Дей­стви­тель­но, пусть Y  — дру­гой участ­ник тур­ни­ра. Если тен­ни­сист X вы­иг­рал у Y, то он круче Y. В про­тив­ном слу­чае Y дол­жен был про­иг­рать кому-то из со­пер­ни­ков, у ко­то­рых X вы­иг­рал, иначе Y одер­жал бы боль­ше побед, чем X. Мы снова по­лу­ча­ем, что X круче Y, и лемма до­ка­за­на.

Рас­смот­рим те­перь тур­нир, удо­вле­тво­ря­ю­щий у сло­вию за­да­чи. Пусть тен­ни­сист A одер­жал в нем наи­боль­шее число побед. В Силу леммы A круче всех. Обо­зна­чим число побед A через k и за­ме­тим, что по­сколь­ку A вы­иг­рал не все матчи. Пред­по­ло­жим, что A по­бе­дил тен­ни­си­стов и про­иг­рал cопер­ни­кам Если учи­ты­вать толь­ко ре­зуль­та­ты игр между то в этом мини-тур­ни­ре по лемме най­дет­ся участ­ник C*, ко­то­рый круче всех. Кроме A про­иг­ра­ли. Таким об­ра­зом, C* круче осталь­ных участ­ни­ков всего тур­ни­ра.

За­ме­тим, что по усло­вию C* дол­жен про­иг­рать кому-то из со­пер­ни­ков. Пусть   — все участ­ни­ки, вы­иг­рав­шие у C*. По лемме в мини-тур­ни­ре най­дет­ся тен­ни­сист D*, ко­то­рый круче всех. Кроме того, D* круче лю­бо­го участ­ни­ка E не из этого мини-тур­нир а, по­сколь­ку D* вы­иг­рал у C*, а C*  — у E. Зна­чит, D* круче осталь­ных участ­ни­ков всего тур­ни­ра.

Таким об­ра­зом, все­гда су­ще­ству­ют по край­ней мере три тен­ни­си­ста (A, C* и D*), ко­то­рые круче всех. При­ве­дем при­мер тур­ни­ра, в ко­то­ром таких участ­ни­ков ровно 3. Пусть трое тен­ни­си­стов одер­жа­ли по одной по­бе­де в лич­ных встре­чах и вы­иг­ра­ли у всех осталь­ных. Тогда каж­дый из этой трой­ки круче всех, но никто из осталь­ных участ­ни­ков их не круче.

Ответ: 3.

Сна­ча­ла по­ка­жем, что най­дет­ся игрок, одер­жав­ший не менее семи побед. Дей­стви­тель­но, в про­тив­ном слу­чае общее число побед всех иг­ро­ков было бы не более Но общее число побед равно числу всех сыг­ран­ных пар­тий, то есть равно   — про­ти­во­ре­чие.

Вы­бе­рем тен­ни­си­ста, ска­жем, А, одер­жав­ше­го не менее 7 побед. Уда­лим (вре­мен­но из рас­смот­ре­ния) А и се­ме­рых, про­иг­рав­ших ему. Оста­нет­ся груп­па из 6 тен­ни­си­стов. Рас­суж­дая ана­ло­гич­но, в этой груп­пе най­дем иг­ро­ка В, ко­то­рый вы­иг­рал не менее трёх пар­тий у иг­ро­ков из этой груп­пы. Если убрать из рас­смот­ре­ния В и троих, про­иг­рав­ших ему, оста­нут­ся два тен­ни­си­ста. Из этих двоих вы­бе­рем того, ска­жем, С, кто по­бе­дил дру­го­го. Тогда трой­ка иг­ро­ков А, В, С будет ис­ко­мой по по­стро­е­нию (пер­вые се­ме­ро, уда­лен­ные из рас­смот­ре­ния, про­иг­ра­ли А, уда­лен­ная груп­па из троих про­иг­ра­ла B, и по­след­ний про­иг­рал C).

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

За­фик­си­ру­ем ко­ли­че­ство на­бран­ных очков ко­ман­да­ми и по­смот­рим на графы, со­от­вет­ству­ю­щие дан­но­му рас­пре­де­ле­нию очков. Среди всех таких гра­фов вы­бе­рем граф G, в ко­то­ром ко­ли­че­ство крас­ных ребер ми­ни­маль­но.

Лемма. B крас­ном под­гра­фе графа G нет сле­ду­ю­щих под­гра­фов:

1)  не­ори­ен­ти­ро­ван­ных цик­лов;

2)  ори­ен­ти­ро­ван­ных путей длины 2;

3)  вер­шин сте­пе­ни 3 и более;

4)  не­ори­ен­ти­ро­ван­ных путей длины 4.

До­ка­за­тель­ство.

По­ка­жем, как можно умень­шить ко­ли­че­ство крас­ных ребер, если есть опи­сан­ные выше под­гра­фы.

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

2.  Пред­по­ло­жим, что в G есть крас­ный ори­ен­ти­ро­ван­ный путь длины 2. Тогда можно счи­тать, что ребро между на­ча­лом пути и кон­цом  — синее. Если ребро было на­прав­ле­но от на­ча­ла к концу, то по­ме­ня­ем цвет всех трех ребер, а если из конца в на­ча­ло, то по­ме­ня­ем цвет и ори­ен­та­цию всех трех ребер. За­ме­тим, что такое пре­об­ра­зо­ва­ние не ме­ня­ет ко­ли­че­ство очков, на­бран­ных ко­ман­дой, но умень­ша­ет ко­ли­че­ство крас­ных ребер.

3.  Пред­по­ло­жим, что в G есть вер­ши­на A крас­ной сте­пе­ни 3 или более. Тогда вы­бе­рем трех ее со­се­дей B, C, D. При этом можно счи­тать, что все три крас­ных ребра ис­хо­дят из вер­ши­ны A (слу­чай, когда на­прав­ле­ния раз­лич­ны, не­воз­мо­жен из-за от­сут­ствия пути длины 2, а слу­чай трех вхо­дя­щих ана­ло­ги­чен), а ребра между вер­ши­на­ми B, C, D синие.

Не огра­ни­чи­вая общ­но­сти, можно счи­тать, что ребра ведут из B в C и из C в D. По­лу­ча­ет­ся два слу­чая: в пер­вом ребро ведет из B в D, а во вто­ром из D в B.

Тогда со­трем все ребра между A, B, C, D и на­ри­су­ем за­но­во сле­ду­ю­щим об­ра­зом:

В обоих слу­ча­ях ри­су­ем синие ребра из B в A, из A в C, из A в D. В пер­вом слу­чае про­ве­дем крас­ные из B в D и из B в C и синее из C в D. Во вто­ром слу­чае про­во­дим крас­ные из D в B и из D в C и синее из C в B.

Итого рас­пре­де­ле­ние очков не по­ме­ня­лось, а ко­ли­че­ство крас­ных ребер умень­ши­лось.

4.  Пред­по­ло­жим, что есть не­ори­ен­ти­ро­ван­ный крас­ный путь длины 4: A, B, C, D, E. Тогда можно счи­тать, что крас­ные ребра ори­ен­ти­ро­ва­ны сле­ду­ю­щим об­ра­зом: а остав­ши­е­ся ребра синие.

Если A обыг­ра­ла D, то можно из­ме­нить ребра AB, BC, CD, AD сле­ду­ю­щим об­ра­зом: ребра сде­ла­ем си­ни­ми, а ребра   — крас­ны­ми. Рас­пре­де­ле­ние очков не по­ме­ня­лось, а ко­ли­че­ство крас­ных ребер умень­ши­лось, по­это­му далее можно счи­тать, что D вы­иг­ра­ла у A, а B вы­иг­ра­ла у E.

Если B обыг­ра­ла D, то из­ме­ним ребра AB, AD, BC, BD, CD сле­ду­ю­щим об­ра­зом: ребра сде­ла­ем си­ни­ми, a   — крас­ны­ми.

Если D обыг­ра­ла B, то из­ме­ним ребра BC, BD, BE, CD, DE: ребра сде­ла­ем си­ни­ми, а   — крас­ны­ми.

Рас­пре­де­ле­ние очков не по­ме­ня­лось, ко­ли­че­ство крас­ных ребер умень­ши­лось.

Таким об­ра­зом, граф на крас­ных реб­рах без ори­ен­та­ции яв­ля­ет­ся лесом, в ко­то­ром каж­дое де­ре­во яв­ля­ет­ся це­поч­кой не более чем из 4 вер­шин. Тогда ко­ли­че­ство крас­ных ребер равно где T  — ко­ли­че­ство де­ре­вьев в графе на крас­ных реб­рах. Так как в каж­дом де­ре­ве не более 4 вер­шин, то есть

Рас­смот­рим тур­нир из 4 ко­манд A, B, C, D. Пусть в нем peбра   — крас­ные, а ребра   — синие. Тогда ко­ман­ды A, B на­бра­ли по 7 очков, а ко­ман­ды C, D  — по

За­ме­тим, что при таком рас­пре­де­ле­нии очков долж­но быть сыг­ра­но не менее 3 овер­тай­мов, так как в до­пол­ни­тель­ное время долж­ны за­кон­чит­ся матчи между A и B и между C и D, так как A и B не могли про­иг­рать в ос­нов­ное время, а C и D не могли по­бе­дить в ос­нов­ное время. Если все остав­ши­е­ся матчи за­вер­ши­лись в ос­нов­ное время, то сум­мар­ное ко­ли­че­ство очков у A и B будет крат­но 3  —про­ти­во­ре­чие.

Разо­бьем 2016 ко­манд на чет­вер­ки (A₁, B₁, C₁, D₁), ..., (A₅₀₄, B₅₀₄, C₅₀₄, D₅₀₄). Пусть внут­ри чет­ве­рок матчи за­кон­чи­лись так, как опи­са­но выше, а при ко­ман­да из i-й чет­вер­ки по­беж­да­ет ко­ман­ду из j-й в ос­нов­ное время. Тогда из по­лу­чен­но­го рас­пре­де­ле­ния очков можно сде­лать вывод, что ко­ман­да из i-й чет­вер­ки дей­стви­тель­но по­беж­да­ет ко­ман­ду из j-й в ос­нов­ное время. В опи­сан­ном слу­чае внут­ри каж­дой чет­вер­ки будет рас­пре­де­ле­ние очков 7, 7, 2, 2, по­это­му будет не менее 3 овер­тай­мов, а зна­чит, всего овер­тай­мов не менее 1512.

Ответ:

Всего в ходе тур­ни­ра было сыг­ра­но пар­тий, то есть разыг­ра­но столь­ко же очков. По усло­вию Вася про­иг­рал одну пар­тию, по­это­му с 10 участ­ни­ка­ми он сыг­рал либо вни­чью, либо вы­иг­рал. Зна­чит, он на­брал не менее 5 очков. Тогда каж­дый из осталь­ных на­брал не менее очков, а все шах­ма­ти­сты в сумме на­бра­ли не менее

очков. Это воз­мож­но толь­ко в слу­чае, если за­няв­ший пер­вое место Петя на­брал 6 очков, Вася на­брал 5 очков, а осталь­ные участ­ни­ки  — по очков.

Ответ: на одно.

Пред­по­ло­жим, что в каком-то туре не было игры между зем­ля­ка­ми. Тогда участ­ни­ки раз­би­ва­ют­ся на пары людей из раз­ных го­ро­дов. Рас­смот­рим про­из­воль­но­го участ­ни­ка. В каж­дой паре есть не более од­но­го его зем­ля­ка, также вто­рой участ­ник из его пары не яв­ля­ет­ся его зем­ля­ком. Но тогда всего зем­ля­ков у него мень­ше по­ло­ви­ны из всех участ­ни­ков. Зна­чит, каж­дый участ­ник сыг­рал боль­ше игр с не­зем­ля­ка­ми, чем с зем­ля­ка­ми, и в сумме игр между зем­ля­ка­ми было мень­ше по­ло­ви­ны. Про­ти­во­ре­чие.

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

На­зо­вем его Ан­дре­ем. Рас­смот­рим тех, у кого он вы­иг­рал. Пусть это будут Боря, Вася, Гриша и Дима. В мат­чах между ними было сыг­ра­но 6 пар­тий, по­это­му кто-то из них одер­жал хотя бы две по­бе­ды. Пусть для опре­де­лен­но­сти это будет Боря и вы­иг­рал он у Васи и Гриши. Тогда рас­смот­рим чет­вер­ку иг­ро­ков Ан­дрей, Боря, Вася и Гриша. Ан­дрей в мат­чах между этими че­тырь­мя иг­ро­ка­ми все матчи вы­иг­рал, по­это­му на­брал три очка, Боря вы­иг­рал ровно два матча, по­это­му на­брал два очка, по­бе­ди­тель матча Васи с Гри­шей на­брал одно, а про­иг­рав­ший очков не на­брал.

По­это­му у них в мат­чах друг с дру­гом на­бра­но раз­ное ко­ли­че­ство очков и, зна­чит, такая чет­вер­ка не удо­вле­тво­ря­ет усло­вию за­да­чи. Сле­до­ва­тель­но, иг­ро­ков не боль­ше семи.

Ответ: 7 тен­ни­си­стов.

Всего ко­ман­да­ми сыг­ра­на игра, в каж­дой из ко­то­рых разыг­ры­ва­лось 2 или 3 очка. Сле­до­ва­тель­но, мак­си­маль­ное ко­ли­че­ство очков, ко­то­рое сум­мар­но может быть у всех ко­манд это Зна­чит, ко­ли­че­ство вы­шед­ших в сле­ду­ю­щий этап ко­манд n удо­вле­тво­ря­ет не­ра­вен­ству от­ку­да

С дру­гой сто­ро­ны, можно при­ве­сти при­мер тур­нир­ной таб­ли­цы, в ко­то­рой 4 ко­ман­ды от­би­ра­ют­ся в сле­ду­ю­щий круг (см. таб­ли­цу).

Ответ: 4.

Всего ко­ман­да­ми сыг­ра­на игр, в каж­дой из ко­то­рых разыг­ры­ва­лось 2 или 3 очка. Сле­до­ва­тель­но, мак­си­маль­ное ко­ли­че­ство очков, ко­то­рое сум­мар­но может быть у всех ко­манд это Зна­чит, ко­ли­че­ство вы­шед­ших в сле­ду­ю­щий этап ко­манд n удо­вле­тво­ря­ет не­ра­вен­ству от­ку­да

C дру­гой сто­ро­ны, можно при­ве­сти при­мер тур­нир­ной таб­ли­цы, в ко­то­рой 5 ко­манд от­би­ра­ют­ся в сле­ду­ю­щий круг:

Ответ: 5.

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

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

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

Под­став­ляя по­лу­ча­ем, что число не­сыг­ран­ных игр не более 100, а число всех воз­мож­ных игр от­ку­да число сыг­ран­ных игр не менее

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

Ответ: 90 игр.

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

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

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

Под­став­ляя по­лу­ча­ем, что число не­сыг­ран­ных игр не более 64, а число всех воз­мож­ных игр от­ку­да число сыг­ран­ных игр не менее

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

Ответ: 56 игр.

За­ме­тим, что борец с но­ме­ром k может про­иг­рать толь­ко борцу с но­ме­ром или по­это­му после каж­до­го тура наи­мень­ший номер не может уве­ли­чить­ся боль­ше, чем на 2 но­ме­ра. На тур­ни­ре с 256 участ­ни­ка­ми 8 туров, сле­до­ва­тель­но, номер по­бе­ди­те­ля тур­ни­ра не пре­вос­хо­дит

Пред­по­ло­жим, что борец с но­ме­ром 17 может по­бе­дить. Тогда в пер­вом туре долж­ны вы­быть борцы с но­ме­ра­ми 1 и 2. Это воз­мож­но толь­ко если борец с но­ме­ром 1 про­иг­рал борцу с но­ме­ром 3, а борец с но­ме­ром 2 про­иг­рал борцу с но­ме­ром 4. Зна­чит, после пер­во­го тура борцы с но­ме­ра­ми 3 и 4 оста­нут­ся. Ана­ло­гич­но, после вто­ро­го тура оста­нут­ся борцы с но­ме­ра­ми 5 и 6, после тре­тье­го  — 7 и 8, ..., после седь­мо­го  — 15 и 16. Зна­чит, в по­след­нем, фи­наль­ном, бою встре­тят­ся борцы с но­ме­ра­ми 15 и 16. Про­ти­во­ре­чие с пред­по­ло­же­ни­ем, что борец с но­ме­ром 17 может по­бе­дить.

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

Ответ: 16.