=====ММ41=====

**Конкурсная задача ММ41** (3 балла)

Двое играют в такую игру:\\
Игроки A и B выставляют на кон по банкноте одинакового достоинства, на каждой из которых имеется семизначный номер. Игроки сравнивают соответствующие (стоящие в одинаковых позициях) цифры номеров. Если i-я цифра на банкноте игрока A больше i-й цифры на банкноте B, то A получает зачетный балл.
Побеждает (и забирает банкноту противника) тот, кто наберет больше зачетных баллов. В случае равенства баллов игроки остаются при своих.
Например, если у A номер банкноты 4987200, а у B - 4007311, то со счетом 3:2 победит B.\\
Какую наименьшую сумму цифр может иметь номер банкноты, для которой математическое ожидание выигрыша положительно?

**Решение**

Ясно, что математическое ожидание выигрыша положительно для тех номеров n, для которых положительно число v(n) - f(n), где v(n) - количество номеров, у которых данный номер выигрывает, а f(n) - количество номеров, которым данный номер проигрывает.
Может показаться, что математическое ожидание выигрыша положительно для тех и только тех номеров, у которых сумма цифр больше математического ожидания суммы цифр произвольного номера (т.е. числа 31.5). Однако это не так.

Проиллюстрирую это на примере трехзначных номеров.\\
Ясно, что v(n) = v3(n) + v2(n) + v1(n), где v3(n) - количество номеров, у которых данный номер выигрывает со счетом 3:0; v2(n) - количество номеров, у которых данный номер выигрывает со счетом 2:1 или 2:0; v1(n) - количество номеров, у которых данный номер выигрывает со счетом 1:0.
Пусть номер n данного билета записывается цифрами a, b, и c. Тогда v3(n) = abc; v2(n) = ab(10-c) + a(10-b)c + (10-a)bc; v1(n) = a + b + c. Аналогично f(n) = (9-a)(9-b)(9-c) + (9-a)(9-b)(c+1) + (9-a)(b+1)(9-c) + (a+1)(9-b)(9-c) + 27 - a - b - c.
Для номера 760, сумма цифр которого меньше мат. ожидания суммы цифр трехзначного номера, имеем v(760) = 433, f(760) = 416.


Для семизначных номеров можно рассуждать аналогичные рассуждения будут слишком громоздки. Поэтому зададим производящие функции для v(a,b,c) и f(a,b,c).\\
Легко понять, что в выражении (1+ax+(9-a)/x)(1+bx+(9-b)/x)(1+cx+(9-c)/x) после раскрытия скобок сумма коэффициентов при положительных степенях x будет равна v(a,b,c), при отрицательных степенях x  -  f(a,b,c), а  свободный член, количеству чисел, с которыми наше число сыграет вничью.\\
v(8887000) - f(888700) = 370665 и, значит, математическое ожидание выигрыша для номера 8887000, имеющеего сумму цифр 31, положительно.

Перебирая (разумеется, на компьютере и, разумеется, с точностью до порядка цифр) v(n) - f(n), для номеров, имеющих сумму цифр 30, убеждаемся, что для них мат. ожидание выигрыша всегда отрицательно.
Ответ - 31.

**Обсуждение**

С точностью до перестановки цифр существует всего 7 номеров с суммой 31, для которых v(n) > f(n). Это номера 9976000, 9886000, 9877000, 9777100, 8887000, 8886100 и 8877100.

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

Назовем кортеж из n цифр (в системе счисления с основанием g) парадоксальным, если номер купюры, образованный цифрами кортежа, имеет положительное математическое ожидание выигрыша и при этом сумма элементов кортежа меньше n(g-1)/2.\\
Ясно, что порядок элементов роли не играет, т.е. речь идет о мультимножествах.\\
Степенью парадоксальности парадоксального кортежа k назовем число d = n(g-1) - 2s, где s - сумма элементов кортежа.\\
Коэффициент парадоксальности кортежа - отношение количества номеров, проигрывающих данному, к количеству выигрывающих.

В этой терминологии в задаче ММ41 речь идет парадоксальных номерах степени парадоксальности 1.

Парадоксальные номера существуют для всех систем счисления, за исключением систем с основаниями 2, 3, 4, 5, 6, 7, 9, 11.

В десятичной системе степень парадоксальности кортежа не может превышать 1. При достаточно больших g степень парадоксальности может быть сколь угодно велика.\\
Например, при g = 101 кортеж состоящий из 10-и цифр 98, 15-и цифр 47 и 24-х нулей имеет степень парадоксальности 30.

Коэффициент парадоксальности ограничен сверху (стремится к некому пределу с ростом g). Точного значения этого предела я не знаю. Мне известны примеры, показывающие, что коэффициент парадоксальности может быть больше 1.532754 

**Награды**

По-видимому, я поскупился, оценив данную задачу в 3 балла. Я полагал, что буду поощрять дополнительными баллами тех марафонцев, которым удастся найти решения, менее чем вышеизложенное зависящее от компьютерного перебора. Но таковых не нашлось.\\
Правильный ответ нашли Влад Франк и Олег Полубасов. В их решениях указывается на наличие номеров с суммой 31 и положительным математическим ожиданием выигрыша, но, к сожалению, ничего не говорится, об отсутствии таких номеров с меньшей суммой цифр. Влад Франк и Олег Полубасов получают по 2 призовых балла.\\
Остальные марафонцы, откликнувшиеся на задачу №41, прислали разной степени "строгости" "доказательства" того, что математическое ожидание выигрыша положительно, начиная с суммы 32, или вовсе ограничились уточнением условий. Они призовых баллов не получают. 
----