Нижегородская олимпиада: Задачи олимпиады

Миша часто ездит в маршрутках. Миша законопослушный, поэтому он всегда покупает билет. Каждый билет в маршрутке имеет номер — \(2N\)-значное десятичное число, возможно, с ведущими нулями. После покупки билета Миша всегда проверяет, счастливый ли достался ему билет. Счастливым Миша считает такой билет, у которого сумма первых \(N\) цифр номера равна сумме последних \(N\) цифр. Если билет оказывается несчастливым, Миша ищет расстояние до ближайшего счастливого, т.е. минимальное число \(x\) такое, что если к номеру билета, полученного Мишей, прибавить или отнять \(x\) (при этом, разумеется, полученный номер должен быть корректным номером билета, т.е. должен быть не меньше нуля и не больше \(10^{2N}-1\)), то получившийся номер должен быть номером счастливого билета.

Билеты, у которых это расстояние максимально среди всех возможных, Миша называет совершенно несчастливыми. Мише очень интересно, сколько всего существует совершенно несчастливых билетов и какие номера у этих билетов. Но так как Миша плохо учился в школе, он не знает, как решать такую задачу, поэтому он обратился за помощью к вашему другу, специалисту по маршруткам. Он же перенаправил Мишу к вам.