===== №70 ===== **Конкурсная задача №70 ** (12 баллов) В k-круговом шахматном блицтурнире приняли участие n шахматистов. В итоговой таблице никакие два участника не набрали поровну очков (т.е. в терминах задачи 48 турнир оказался строгим).\\ На торжественном закрытии турнира участник, занявший последнее место, заметил, что, если бы очки начислялись так же как в футболе, он занял бы не последнее, а первое место.\\ Более того, при подсчете очков по футбольным правилам, никакие два участника по-прежнему не имели бы поровну очков, но при этом выстроились бы в итоговой таблице в обратном порядке. 1. Какое наименьшее число партий могло быть сыграно в таком турнире?\\ 2. При каком наименьшем k возможна описанная ситуация?\\ 3. При каком наименьшем n достигается наименьшее k, при котором возможна такая ситуация. Примечания:\\ В k-круговом турнире каждый участник встречается с каждым k раз.\\ За победу в партии в шахматном турнире начисляется одно очко, за ничью пол-очка, а за поражение ноль очков.\\ За победу в матче в в футбольном турнире начисляется три очка, за ничью одно очко, а за поражение ноль очков.\\ Разумеется, в турнире участвует более одного шахматиста. ** Решение ** Турниры, о которых идет речь в условии задачи будем называть "перевертышами". Для удобства будем считать, что за победу шахматист получает 2 очка, а за ничью - 1. Такую систему подсчета очков будем называть "старой", а футбольную (3 очка за победу) - "новой". Места команд (если иное не оговорено особо) будем называть по старой системе. Лемма: k>5\\ Пусть участник A выиграл v, свел вничью s и проиграл d партий. Тогда участник В, отставший от него на одно очко по старой системе и опередивший на одно очко по новой, должен был выиграть v+2, сыграть вничью s-5 и проиграть d+3 партии. Даже если предположить, что все участники расположились в турнирных таблицах (и по старой, и по новой системе) максимально плотно, и, что у последнего совсем нет ничьих, у первого все равно должно быть не менее 5*(n-1) ничьих. Общее число партий, сыгранных одним участником равно k*(n-1). Участник, занявший первое место не мог завершить все партии вничью, поэтому k*(n-1) > 5*(n-1), т.е. k>5. 1. 30 партий.\\ Ясно, что "турнир" из двух участников не может быть перевертышем.\\ Из леммы следует, что при n>3 в турнире перевертыше должно быть не менее C(n,4)*6 = 36 партий.\\ При n = 3 существует турнир-перевертыш из 10 кругов и 30 партий.\\ Вот его итоговая таблица: ^ ^ 1 ^ 2 ^ 3 ^Пб^Нч^Пр^O1 02^ |1.|XXXXXXX|+0=10-0|+3=5-2 |3 |15| 2|21 24| |2.|+0=10-0|XXXXXXX|+5=0-5 |5 |10| 5|20 25| |3.|+2=5-2 |+5=0-5 |XXXXXXX|7 |5 | 8|19 26| Менее чем 10 кругов в турнире-перевертыше из трех команд быть не может. В самом деле, победитель должен была сыграть вничью, по крайней мере, на 5 партий больше, чем второй. Сделать 5 лишних ничьих он мог только с аутсайдером. Но у участника, занявшего второе место должно быть на 5 ничьих больше, чем у аутсайдера. Поэтому первый и второй призеры должны были сыграть между собой вничью не менее 10 раз и, значит, в турнире не менее 10 кругов. 2. k = 6.\\ Из леммы следует, что меньше 6 кругов в турнире-перевертыше быть не может. Приведем таблицу 6-крувого турнира-перевертыша: ^ ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^Пб^Нч^Пр^О1 О2^ |1.|XXXX|+0=6|+0=6|+0=6|+0=6|+0=6|+1=5|+1=5|+1=5|+1=5|+1=5|5 |55| 0|65 70| |2.|+0=6|XXXX|+0=6|+0=6|+0=6|+0=6|+1=5|+1=5|+1=5|+1=5|+3=0|7 |50| 3|64 71| |3.|+0=6|+0=6|XXXX|+0=6|+0=6|+0=6|+1=5|+1=5|+1=5|+3=0|+3=0|9 |45| 6|63 72| |4.|+0=6|+0=6|+0=6|XXXX|+0=6|+0=6|+1=5|+1=5|+3=0|+3=0|+3=0|11|40| 9|62 73| |5.|+0=6|+0=6|+0=6|+0=6|XXXX|+0=6|+1=5|+3=0|+3=0|+3=0|+3=0|13|35|12|61 74| |6.|+0=6|+0=6|+0=6|+0=6|+0=6|XXXX|+3=0|+3=0|+3=0|+3=0|+3=0|15|30|15|60 75| |7.|+0=5|+0=5|+0=5|+0=5|+0=5|+3=0|XXXX|+3=0|+3=0|+4=0|+4=0|17|25|18|59 76| |8.|+0=5|+0=5|+0=5|+0=5|+3=0|+3=0|+3=0|XXXX|+3=0|+3=0|+4=0|19|20|21|58 77| |9.|+0=5|+0=5|+0=5|+3=0|+3=0|+3=0|+3=0|+3=0|XXXX|+3=0|+3=0|21|15|24|57 78| |10|+0=5|+0=5|+3=0|+3=0|+3=0|+3=0|+2=0|+3=0|+3=0|XXXX|+3=0|23|10|27|56 79| |11|+0=5|+3=0|+3=0|+3=0|+3=0|+3=0|+2=0|+2=0|+3=0|+3=0|XXXX|25| 5|30|55 80| 3. n = 11.\\ В предыдущем пункте приведена таблица 6-крувого турнира-перевертыша с 11 участниками. Покажем, что при меньших n, 6-крувого турнира-перевертыша не существует. Отдельно рассмотрим случаи четного и нечетного n. 1) n = 2s+1. Каждый участник сыграл по 12s партий.\\ В этом случае возможен плотный (когда соседей по таблице отделяет друг от друга одно очко) 6-круговой турнир. В таком турнире у победителя 13s, а у аутсайдера 11s очков. Пусть аутсайдер такого турнира сыграл вничью x партий.\\ Тогда участник, занявший предпоследнее место - x+5 партий;\\ участник, занявший третье с конца место - x+10 партий;\\ ............................\\ победитель - x+10s партий. Для того чтобы набрать 13s очков, победитель должен выиграть не менее s партий. Поэтому 12s-(x+10s) ≥ s, откуда x ≤ s.\\ Кроме того, числа x и s должны быть одной четности (иначе в общее число ничьих в турнире не будет целым). Просуммируем ничьи, сделанные первыми s участниками:\\ (x+5s+5) + (x+5s+10) + ... + (x+10s) = s*(2x+15s+5)/2.\\ Допустим, что первые s участников сыграли все партии между собой вничью. Это составит 6s*(s-1) ничьих.\\ Тогда a = s*(2x+15s+5)/2 - 6s*(s-1) = s*(3*s+2x+17)/2 приходится на ничьи, сыгранные s лидерами с остальными участниками. Ясно, что это число не должно превышать общего количества ничьих участников, занявших места с s+1-го по последнее,\\ т.е. b = x + (x+5) + ... + (x+5s) = (2x+5s)*(s+1)/2.\\ Иными словами, b-a = s2 - 6s + x должно быть неотрицательно.\\ Ясно, что это невозможно при s<5 (напомню, что x ≤ s).\\ Впервые b-a становится неотрицательным при s = x = 5, что, как раз, соответствует приведенному выше примеру. Ясно, что, если турнир-перевертыш не является плотным (хотя бы по одной из систем), то минимальное s, которое в приведенном примере достигается "впритык", может только увеличиться. 2) n = 2s. В этом случае, турнир не может быть плотным по старой системе. В самом деле, если бы турнир был плотным, один из участников набрал бы ровно половину возможных очков - n-1. Но тогда по соображениям симметрии для каждого участника, набравшего n-1+x очков, найдется участник, набравший n-1-x очков. Но это противоречит четности числа участников. Итак, в итоговом положении турнира-перевертыша с четным числом участников должен быть хотя бы один просвет в 2 очка (между участниками, занявшими s-е и s+1-е места). Этот просвет отвечает скачку в 8 ничьих, т.е. участника, набравшего по старой системе на два очка меньше, а по новой - на очко больше, должно быть на 8 ничьих меньше, на 3 победы и на 5 поражений больше. Наиболее плотное распределение ничьих (от последнего места к первому): x, x+5, ..., x+5*(s-1), x+5s+3, ..., x+10s-7, x+10s-2. (В этом случае тоже не сложно найти ограничения для x, но они не существенны для дальнейших рассуждений.) Как и в предыдущем случае, допустим, что s участников из верхней половины таблицы завершили все свои партии вничью. Тогда с участниками из нижней части таблицы они сделали a = (x+5s+3) +...+ (x+10s-7) + (x+10s-2) - 6s*(s-1) ничьих.\\ В то же время, последние s участников сделали b = x + (x+5) + ... + (x+5s-5) ничьих.\\ Учитывая, что b-a = 2s-18 должно быть неотрицательным, получим, что при четном числе участников в турнире-перевертыше должно быть занято не менее 18 шахматистов.\\ Замечу (хотя это и не важно для строгости решения), что пример 6-кругового турнира-перевертыша для 18 участников легко строится. **Обсуждение** Составляя аналог выражения b-a для других k и n и требуя его неотрицательности, легко получить наименьшие возможные k для всех n (и наименьшие n для всех k): ^ n ^ k ^ | 2 | - | | 4 | 13 | | 3 | 10 | | 6 | 9 | | 5, 8 | 8 | | 7, 9, 10, 12, 14, 16 | 7 | | 11, 13, 15, 17, 18,... | 6 | Любопытно, что условие неотрицательности b-a, фигурировавшее в наших рассуждениях, как необходимое для существования турнира-перевертыша, всякий раз оказывается и достаточным (при подходящих x). **Награды** За правильное решение этой задачи Виктор Филимоненков, Влад Франк, Андрей Богданов и Олег Полубвсов получают по 12, а Сергей Беляев -11 призовых баллов. **Эстетическая оценка задачи - 4.5 балла** ----