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

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

Решение задачи ММ41

Решение

Ясно, что математическое ожидание выигрыша положительно для тех номеров 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, или вовсе ограничились уточнением условий. Они призовых баллов не получают.

---