Часть I - футбольная вводная
Часть II - естественные требования ничьи в матче
Часть III - эквивалентное определение ничьи в матче
Часть IV - "естественность" дополнительного требования
Часть V - "естественность" и недостатки дополнительного требования
В предыдущей заметке была дана эквивалентная формулировка правила определения лучшей команды. Мы обсудили требования 1-3. В этой и следующих заметках мы исследуем в каких условия 1), недостаточно, чтобы определить победителя и почему "дополнительное" требования является "естественным" в некотором смысле. Также мы укажем на некоторые недостатки.
Ниже есть продолжение.
Итак, вспомним ещё раз:
Формулировка правила. Победителем является команда, которая по-сумме двух встреч забила больше голов, чем пропустила. В случае равенства забитых и пропущенных мячей сравниваются количество голов забытых на выезде. В случае и этого равенства, в конце обычный 90 минут игр ("грязного времени") во второй игре, судья назначает дополнительное время и, в случае надобности, пенальти.
Любой счёт между командами A и B может быть записан как a1:b1, a2:b2.
1). Для определение победителя нужно сравнить два выражения (a1+a2) и (b1+b2). Если первое больше второе, то победителем объявляется команда A. Если второе больше первого, то победителем объявляется команда B. В случае ничьей, для определения победителя переходим к следующему правилу.
Второе, сравниваются количество голов забытых на выезде, в наших обозначениях может быть записано так:
2) Если a2 больше чем b1, то победителем является команда A. Если меньше-команда B. Если они равны, фиксируется ничья (дополнительное время и пенальти).
Дополнительное требование ("дома и стены помогают"). В случае равенства основных показателей, предпочтение должно быть отдано команде, которая забила больше голов на чужом поле.
Заметим, что дополнительное требование полностью эквивалентно условию 2 из второго условия определения победителя.
Заметим, что следующие выражения эквивалентны (вместо > может быть >=, < <= или =):
(a1+a2) > (b1+b2)
(a1+a2) - (b1+b2) > 0
(a1-b1) - (b2-a2) > 0
(a1-b1) > (b2-a2)
Теперь зададим такой вопрос: перечислить, в некотором смысле, все возможные счета матчей при которых только с помощью 1) т.е. без дополнительного требования невозможно определить победителя, т.е. мы получаем "ничью". Что значит фраза "в некоторым смысле" будет понятно позже.
"Ничья" получается, согласно 1) когда выражения (a1+a2) и (b1+b2) равны. Т.е.
(*) a1+a2=b1+b2
или, что эквивалентно
b2=a1-b1+a2
Перед тем, как продолжить введём новую нотацию. Будем говорить, что четвёрка чисел является решением уравнение (*) в том смысле, если подставить их в уравнение (*) мы получим верное равенство. Пример, такой четвёрки чисел является (1,2,2,1). Имеется в виду, что a1=1, a2=2, b1=2, b2=1. Естественно, что все четыре числа должно быть целыми положительными числами или нулём.
Заметим также что четвёрка чисел (1,2,2,1), также однозначно задаёт счёт матча: 1:2, 2:1. И наоборот любой счёт, который привёл к ничье, скажем, 1:1, 2:2, может быть записан как такая четвёрка (1,1,2,2).
Что мы имеем? Вопрос, о том, при каком счёте, только с помощью 1) мы не сможем выявить победителя мы свели (говорят, сделали редукцию) к вопросу о нахождение решений уравнения (*)
(*) a1+a2=b1+b2
в неотрицательных числах.
Одним из его решений, как мы видели выше является решение (1,2,2,1), что эквивалентно счёту 1:2, 2:1. Но мы хотим узнать все такие решения. Мы хотим оценить как "часто" мы будет "натыкаться" на такие результаты. Они являются в некоторым смысле плохими результатами, так как нужно вовлекать дополнительное требование для определения победителя.
Из (*) как было показано выше следует
b2=a1-b1+a2
Если внимательно посмотреть на это выражение, оно на самом деле говорить нам следующие. Вы можете выбрать любые значения для a1, b1, a2, но тогда для b2 мы должны взять значение a1-b1+a2. Допустим, вы взяли вместо a1 значение k, вместо b1 взяли n, вместо a2 взяли s. Тогда решением уравнение (*) будет четвёрка (k, n, s, k-n+s).
Замечание: Тут есть один тонкий момент, дело в том, что b2 должно быть b2=0, не бывает отрицательного количества забитых голов, т.е. счёт 3:(-1) "нелегальный". Таким образом, мы должны добавить также условие, что k-n+s>=0.
Ответ: {(k, n, s, k-n+s)| где k,n,s - целые числа, а также k>=0 и n>=0 и s>=0 (и k-n+s>=0)}
Формально это полный и исчерпывающий ответ. Но что он в действительности обозначает?
Давайте, начнём подставлять случайные числа. К примеру, возьмём тройку чисел (2,0,1). Получим, что четвёртое число должно быть 2-0+1=3>=0, т.е. четвёрка чисел будет (2,0,1,3), т.е. если игры закончились со счётом 2:0 и 1:3 мы имеем ничью. Возьмём другую тройку (1,3,1). 1-3+1=-1<0 поэтому четвёрки чисел (1,3,1,-1). Т.е. если мы знаем, что первая игра закончилась со счётом 1:3 и мы знаем, что во-второй игре команда A забила 1 гол, мы заведомо знаем, сколько голов команды B бы не забила "ничьи" не будет. Полезным будет и следующее наблюдение. Если мы возьмём n=0, то выражение k-n+s>=0 всегда (при k>=0 и s>=0). Из этого мы можем сделать вывод, если мы возьмём любую пару чисел (k,s) мы всегда сможем подобрать ещё одну пару чисел, к примеру, (0, k+s), так что у нас будет "ничья". Однако, не для любой тройки чисел мы можем всегда подрать таким образом четвёртое число.
Можем ли "перечислить" все варианты исхода плей-оффа, в котором у нас будет "ничья"? Если нет, можем ли мы хотя бы оценить как часто такие результаты встречаются относительно всех возможных футбольных результатов?
Строго говоря, теоретически, ответом на первый вопрос является нет. Дело в том, что существует бесконечное (но счётное) количество таких четверок. В самом деле, для любого целого k>=0 в ответе будут присутствовать комбинации (k,0,0,k) (k-n+s=k-0+0=k>=0). А таких четвёрок столько же, сколько и натуральных чисел. Т.е. полностью "перечислить" мы не можем (так как такая запись будет бесконечной). Более того, легко доказать, выше я привёл основные этапы такого доказательства, что количество четвёрок, при котором у нас "ничья" является счётным, как и количество четвёрок вообще - всевозможных результатов.
Одним из выходом из создавшейся ситуации мог быть следующий. Да теоретически, Счёт может быть любым, хоть 10:10. Но практически мы можем спокойно предположить, скажем, что он не может быть выше чем 99:99 (я специально взял такой большой запас). Таким образом, мы избавляемся от "кошмара бесконечность". Количество возможных исходов игр становится конечным (равным 100*100=10000), количество "ничьих" становится также конечным (меньше или равно 10000). Вроде бы, достаточно подсчитать количество "ничьих", разделить одно число на другое и искомая оценка будет найдена. Но не так всё просто. При таком подходе, у нас есть очень много результатов, которые на практике не встречаются. К примеру (20, 20, 0, 40), (21,20,0,41), которые существенно искажают результат, но нас на самом деле е интересует. Хорошо, можете сказать вы, давайте снизим планку, давайте считать максимальным счёт 20:20 (даже в двором футболе счёт редко бывает выше). Тогда у нас таких искусственных пар будет меньше, но они всё равно будут. Можно проделать такую работу для "планки 20", затем для "планки 19" и так постепенно понижая планку смотреть как будет меняться наша оценка. Не отрицаю, так можно поступить и быть может, можно будет даже доказать, что наша оценка "сходится" в смысле изложенном выше, когда меняется "планка", к какому-то числу. На этом пути нас ждёт много технических моментов. Во-первых, формально нужно доказать такую "сходимость". Во-вторых, мы всё таки решаем несколько иную задачу, нужно опять-таки формально доказать, что "в пределе" мы получаем исходную задачу. По-мимо этого, такая работа требует довольно много вычислений.
Можно пойти другим путём. Хотя мы не можем "перечислить" всё четверки, которые дают ничьи записав их в явном виде мы можем дать "алгоритм" для такой записи (здесь, я немного жертвую строгостью во имя наглядности). Посмотрим на таблицу "всех" троек чисел (формально, это запись некорректна из-за наличия троеточий):
| (0,0,0) | (0,0,1) | (0,0,2) | ... | (0,1,0) | (0,1,1) | (0,1,2) | ... | (0,2,0) | (0,2,1) | (0,2,2) | ... |
| (1,0,0) | (1,0,1) | (1,0,2) | ... | (1,1,0) | (1,1,1) | (1,1,2) | ... | (1,2,0) | (1,2,1) | (1,2,2) | ... |
| (2,0,0) | (2,0,1) | (2,0,2) | ... | (2,1,0) | (2,1,1) | (2,1,2) | ... | (2,2,0) | (2,2,1) | (2,2,2) | ... |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
Для каждой тройки чисел из этой таблице мы можем вычислить однозначным способом четвёртое число. Если полученное число отрицательное, мы просто отбрасываем такую четвёрку.
Обратим внимание на диагонали нашей таблицы. На диагоналях таблицы сумма чисел k+n+s=const. Первая диагональ состоит только из тройки (0,0,0) для неё 0+0+0=0. Вторая диагональ состоит из двух троек (0,0,1) и (1,0,0) для них имеем сумму 1. Третья диагональ состоит из трёх троек (0,0,2), (1,0,1), (2,0,0) и имеет сумму 2. Отсюда легко получить следующий алгоритм:
а) Для каждого i (i=0,1,2,3...) находим все тройки чисел так что k+n+s=i (k>=0, n>=0, s>=0)
Это будет наша диагональ i. Существенным является то, что количество таких троек конечно (оно на самом деле равно i).
б) Вычисляем r=k-n+s. Если r<0, то отбрасываем всё четвёрку, иначе записываем его.
Покажем, что, таким образом мы перечислим все четвёрки чисел дающих ничью. Такая четвёрка имеем вид (k,n,s, k-n+s), при чём k-n+s>=0 и к>=0, s>=0, n>=0, все числа целые. Найдём сумму i=k+n+s>=0, именно на диагонале i, которой соответствует "большой" шаг i, мы и будем искать нашу четвёрку. Действительно, в пункте a) сказано, что на шаге i мы должны были рассмотреть тройки чисел x,y,z, такие, что x+y+z=i. Так как мы рассматривали все такие тройки, среди них была и "наша тройка" k,n,s. Далее, в пункте б) мы вычислили r=k-n+s. Ну и в "нашей" четверки, четвёртое число равняется k-n+s. Более того, мы знаем, что k-n+s>=0, а значит мы такую четвёрку в пункте б) запишем.
Непонятно написано? Рассмотрим на конкретном примере. К примеру, рассмотрим четвёрку (2,1,1,2). Найдём сумму первых трёх чисел i=2+1+1=4, т.е. это 4-ая диагональ. Т.е. на 4-ом (конечном) "большом" шаге нашего алгоритма, мы должны были рассмотреть тройки чисел k,n,s, такие, что k+n+s=4. Т.к мы рассматривали все такие числа, то среди них были и наши (2,1,1). Далее, в пункте б) мы вычислили r=2-1+1=2. Т.к. 2>=0 мы записали всё четверку (2,1,1,2).
Таким образом, хотя запись выдаваемая нашим алгоритмом остаётся бесконечном, для каждой конкретной четвёрки, которая даёт ничью, мы можем указать за конечное количество шагов за которое оно будет записана. Или, иначе, для каждой конкретной тройки чисел, мы можем указать за конечное количество шагов можно ли её "дополнить" до четверки, чтобы получилась ничья или нет.
В каком-то смысле, вместо 4 параметров, у нас есть только один (диагональ i). Для каждого i мы можем теперь написать оценку и посмотреть как она будет ввести с тебя "в пределе", если i "устремить в бесконечность. Я же этого тут делать не буду.
UPDATE: Вообще-то проще несколько модифицировать этот подход.
а) Для каждого i (i=0,1,2,3...) находим все четвёрки чисел так что k+n+s+t=i (k>=0, n>=0, s>=0, t>=0)
б) Вычисляем r=k-n+s. Если r=t, то записываем такую четвёрки иначе отбрасываем.
(если r<0), то r=t будет заведомо ложным, т.к. t>=0, и мы такую четвёрку отбросим, как и в первоначальном варианте)
Также параллельно мы подсчитываем количество "записанных" и "обработанных" четвёрок. Оценка получится в результате деление одного на другое. Мы можем создать последовательность таких оценок и посмотреть сходится ли она, и если да, то к какому числу.
Покажем, что, таким образом мы перечислим все четвёрки чисел дающих ничью. Такая четвёрка имеем вид (k,n,s, k-s+n), при чём k-n+s>=0 и к>=0, s>=0, n>=0, все числа целые. Найдём сумму i=k+n+s+t>=0, именно на диагонале i, которой соответствует "большой" шаг i, мы и будем искать нашу четвёрку. Действительно, в пункте a) сказано, что на шаге i мы должны были рассмотреть тройки чисел w,x,y,z такие, что w+x+y+z=i. Так как мы рассматривали все такие четвёрки, среди них была и "наша четвёрка" k,n,s,t. Далее, в пункте б) мы вычислили r=k-n+s и сравниваем r с z. Если r=z>=0, то мы запишем такую четвёрку. И действительно, согласно 1) т.к. r=k-n+s такая четвёрка задаёт "ничью".
Я вот написал quick&dirty код на Java который это реализовывает.
package com.blogspot.alexsmail;
public class TieBreak {
public static void main(String[] args) {
int total=0;
int tie=0;
for(int i=0;i<100;i++){
for(int k=0;k<=i;k++){
for(int n=0;n<=i;n++){
for(int s=0;s<=i;s++){
for(int t=0;t<=i;t++){
if(k+n+s+t==i){
//valid 4-tuple
//System.out.println("("+k+","+n+","+s+","+t+")");
total++;
if(k-n+s==t){
//we have tie
tie++;
}
}
}
}
}
}
//System.out.println("total is "+total);
//System.out.println("tie is "+tie);
System.out.println("for i " +i+ " estimation (ratio) is "+((double)tie)/total);
}
}
}
Output:
for i 0 estimation (ratio) is 1.0
for i 1 estimation (ratio) is 0.2
for i 2 estimation (ratio) is 0.2
for i 3 estimation (ratio) is 0.08571428571428572
for i 4 estimation (ratio) is 0.08571428571428572
for i 5 estimation (ratio) is 0.047619047619047616
for i 6 estimation (ratio) is 0.047619047619047616
for i 7 estimation (ratio) is 0.030303030303030304
for i 8 estimation (ratio) is 0.030303030303030304
for i 9 estimation (ratio) is 0.02097902097902098
for i 10 estimation (ratio) is 0.02097902097902098
for i 11 estimation (ratio) is 0.015384615384615385
for i 12 estimation (ratio) is 0.015384615384615385
for i 13 estimation (ratio) is 0.011764705882352941
for i 14 estimation (ratio) is 0.011764705882352941
for i 15 estimation (ratio) is 0.009287925696594427
for i 16 estimation (ratio) is 0.009287925696594427
for i 17 estimation (ratio) is 0.007518796992481203
for i 18 estimation (ratio) is 0.007518796992481203
for i 19 estimation (ratio) is 0.006211180124223602
for i 20 estimation (ratio) is 0.006211180124223602
for i 21 estimation (ratio) is 0.0052173913043478265
for i 22 estimation (ratio) is 0.0052173913043478265
for i 23 estimation (ratio) is 0.0044444444444444444
for i 24 estimation (ratio) is 0.0044444444444444444
for i 25 estimation (ratio) is 0.0038314176245210726
for i 26 estimation (ratio) is 0.0038314176245210726
for i 27 estimation (ratio) is 0.0033370411568409346
for i 28 estimation (ratio) is 0.0033370411568409346
for i 29 estimation (ratio) is 0.002932551319648094
for i 30 estimation (ratio) is 0.002932551319648094
for i 31 estimation (ratio) is 0.0025974025974025974
for i 32 estimation (ratio) is 0.0025974025974025974
for i 33 estimation (ratio) is 0.0023166023166023165
for i 34 estimation (ratio) is 0.0023166023166023165
for i 35 estimation (ratio) is 0.002079002079002079
for i 36 estimation (ratio) is 0.002079002079002079
for i 37 estimation (ratio) is 0.001876172607879925
for i 38 estimation (ratio) is 0.001876172607879925
for i 39 estimation (ratio) is 0.0017016449234259785
for i 40 estimation (ratio) is 0.0017016449234259785
for i 41 estimation (ratio) is 0.0015503875968992248
for i 42 estimation (ratio) is 0.0015503875968992248
for i 43 estimation (ratio) is 0.0014184397163120568
for i 44 estimation (ratio) is 0.0014184397163120568
for i 45 estimation (ratio) is 0.0013026487190620929
for i 46 estimation (ratio) is 0.0013026487190620929
for i 47 estimation (ratio) is 0.0012004801920768306
for i 48 estimation (ratio) is 0.0012004801920768306
for i 49 estimation (ratio) is 0.0011098779134295228
На основании этих данных можно выразить уверенность, что она стремится к нулю. Мы имеем монотонно уыбвающую последовательность.
END OF UPDATE
Продолжение следует.
No comments:
Post a Comment