Обо­зна­чим через S_n мно­же­ство всех тре­бу­е­мых рас­ста­но­вок для таб­ли­цы n × n. Тогда f (n) по опре­де­ле­нию равно ко­ли­че­ству эле­мен­тов в мно­же­стве S_n. Введём опе­ра­цию g над таб­ли­цей, за­клю­ча­ю­щу­ю­ся в уда­ле­нии по­след­не­го (край­не­го пра­во­го) столб­ца и по­след­ней (край­ней ниж­ней) стро­ки таб­ли­цы. При­мер:

Оче­вид­но, если то

а)  Мы до­ка­жем, что отоб­ра­же­ние яв­ля­ет­ся инъ­ек­тив­ным (смысл тер­ми­на будет разъ­яснён далее), и при этом его образ не по­кры­ва­ет всего мно­же­ства S₂₀₁₅. От­сю­да будет сле­до­вать тре­бу­е­мое не­ра­вен­ство.

Утвер­жде­ние 1. Пусть дана таб­ли­ца Тогда су­ще­ству­ет не более одной таб­ли­цы такой, что

До­ка­за­тель­ство. Будем вос­ста­нав­ли­вать таб­ли­цу x по из­вест­ной таб­ли­це

Для на­гляд­но­сти изоб­ра­зим обе таб­ли­цы сле­ду­ю­щим об­ра­зом:

Т. е. пусть по­след­ний стол­бец таб­ли­цы x со­дер­жит не­из­вест­ные числа по­след­няя стро­ка со­дер­жит не­из­вест­ные числа

Число a_i долж­но от­ли­чать­ся от всех чисел в стро­ке с но­ме­ром i таб­ли­цы y. Но в любой стро­ке таб­ли­цы y стоят 2015 раз­лич­ных чисел из мно­же­ства т. е. для a_i остаётся един­ствен­ное воз­мож­ное зна­че­ние. Сле­до­ва­тель­но, все числа од­но­знач­но опре­де­ля­ют­ся по таб­ли­це y. Ана­ло­гич­но, рас­смат­ри­вая столб­цы, од­но­знач­но вос­ста­нав­ли­ва­ем числа b_j.

Если среди вос­ста­нов­лен­ных чисел есть оди­на­ко­вые, по­лу­ча­ем про­ти­во­ре­чие с усло­ви­ем, и, сле­до­ва­тель­но, таб­ли­цы x, удо­вле­тво­ря­ю­щей ра­вен­ству не

су­ще­ству­ет. Если же все a_i раз­лич­ны, и все b_j раз­лич­ны, то число c долж­но от­ли­чать­ся от них всех, и такое число тоже един­ствен­но.

Итак, если таб­ли­ца x су­ще­ству­ет, то она един­ствен­на, что и тре­бо­ва­лось.

След­ствие: если и то (Отоб­ра­же­ние g с таким свой­ством в ма­те­ма­ти­ке на­зы­ва­ет­ся инъ­ек­тив­ным).

Утвер­жде­ние 2. Су­ще­ству­ет таб­ли­ца такая, что любое

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

Вос­ста­нав­ли­вая по ней таб­ли­цу x так же, как то сде­ла­но выше, мы по­лу­ча­ем что про­ти­во­ре­чит усло­вию. Сле­до­ва­тель­но, ис­ко­мой таб­ли­цы x не су­ще­ству­ет.

Из до­ка­зан­ных утвер­жде­ний сле­ду­ет, что в мно­же­стве S₂₀₁₅ боль­ше эле­мен­тов, чем в S₂₀₁₆, т. е.

Про­ил­лю­стри­ру­ем на­гляд­но по­след­ний шаг рас­суж­де­ния. Пред­по­ло­жим, что мы вы­пи­са­ли в ряд все воз­мож­ные таб­ли­цы из мно­же­ства S₂₀₁₆. Рас­смот­рим сле­ду­ю­щую диа­грам­му отоб­ра­же­ния g:

В мно­же­стве S₂₀₁₆ ровно K эле­мен­тов, и все они вы­пи­са­ны в верх­нем ряду. В ниж­нем ряду для каж­дой таб­ли­цы x вы­пи­са­на со­от­вет­ству­ю­щая таб­ли­ца g(x), а также по­стро­ен­ная в утвер­жде­нии 2 таб­ли­ца y. Все таб­ли­цы в ниж­нем ряду при­над­ле­жат мно­же­ству S₂₀₁₅, и все они по до­ка­зан­но­му раз­лич­ны. Сле­до­ва­тель­но, ко­ли­че­ство таб­лиц в мно­же­стве S₂₀₁₅ боль­ше, чем в S₂₀₁₆.

б)  До­ка­жем, что при отоб­ра­же­нии в каж­дую таб­ли­цу мно­же­ства S₁₀₀₈ отоб­ра­жа­ет­ся более одной таб­ли­цы мно­же­ства S₁₀₀₉. От­сю­да будет сле­до­вать тре­бу­е­мое не­ра­вен­ство.

Утвер­жде­ние 3. Пусть дана таб­ли­ца y S₁₀₀₈. Тогда су­ще­ству­ет не менее 1007 раз­лич­ных таб­лиц таких, что

До­ка­за­тель­ство. Так же, как в п. а), изоб­ра­зим на­гляд­но ра­вен­ство :

По­ка­жем, как для за­дан­ной таб­ли­цы по­стро­ить не менее 1007 раз­лич­ных таб­лиц x, удо­вле­тво­ря­ю­щих ра­вен­ству

В объ­еди­не­нии пер­вой стро­ки и пер­во­го столб­ца таб­ли­цы y на­пи­са­но 2015 чисел (не­обя­за­тель­но все раз­лич­ные), по тому су­ще­ству­ет число из мно­же­ства ко­то­ро­го нет ни в пер­вой стро­ке, ни в пер­вом столб­це таб­ли­цы y. По­ло­жим a₁ и b₁ рав­ны­ми тому числу. Т. е. со­глас­но на­ше­му вы­бо­ру a₁ = b₁.

Для будем по­сле­до­ва­тель­но вы­би­рать числа a_i так, чтобы число a_i не рав­ня­лось ни од­но­му из чисел в i-й стро­ке таб­ли­цы y, а также не рав­ня­лось уже вы­бран­ным чис­лам Такой выбор все­гда су­ще­ству­ет, т. к. "за­прещёнными" ока­зы­ва­ют­ся все­гда не более 1008 + 1007 = 2015 чисел.

Ана­ло­гич­но для будем по­сле­до­ва­тель­но вы­би­рать числа b_j так, чтобы число b_j не рав­ня­лось ни од­но­му из чисел в j-м столб­це таб­ли­цы y, а также не рав­ня­лось чис­лам

Мы из­на­чаль­но вы­бра­ли a₁ = b₁, по­это­му среди чисел a_i, b_j, i, j = 1 . . . 1008, не более 2015 раз­лич­ных. По тому можно вы­брать число c от­лич­ным от них всех, и тем самым за­вер­шить по­стро­е­ние таб­ли­цы x. По­стро­ен­ная таб­ли­ца x удо­вле­тво­ря­ет всем усло­ви­ям за­да­чи и при­над­ле­жит мно­же­ству S₁₀₀₉, при том

За­ме­тим, что при вы­бо­ре числа a₂ за­прещёнными были не более 1009 чисел (числа во вто­рой стро­ке таб­ли­цы y и число a₁). По­это­му име­лось не менее 1007 спо­со­бов вы­брать число a₂, и все они при­ве­ли бы к раз­лич­ным таб­ли­цам x. Сле­до­ва­тель­но, таких таб­лиц x, для ко­то­рых не менее 1007, что и тре­бо­ва­лось до­ка­зать.

Ответ: а) f (2015) > f (2016), б) f (1009) > f (1008).