На про­тя­же­нии этого ре­ше­ния число со­че­та­ний из n по k обо­зна­ча­ет­ся чи­та­те­лей, более при­вык­ших к но­та­ции про­сим об­ра­щать вни­ма­ние на «пе­ре­вер­ну­тый» по­ря­док ин­дек­сов:

Итак, нам тре­бу­ет­ся найти число пар и таких что при­чем вы­пол­ня­ют­ся три со­от­но­ше­ния при Наше ре­ше­ние за­да­чи со­сто­ит из двух эта­пов:

Утвер­жде­ние 1. Пары объ­ек­тив­но со­от­вет­ству­ют чет­вер­кам таким что и

Ком­мен­та­рий 1. Го­во­ря более раз­вер­ну­то, в Утвер­жде­нии 1 ска­за­но сле­ду­ю­щее: у каж­дой удо­вле­тво­ря­ю­щей усло­вию за­да­чи пары (N₁, N₂) их цифры (b₁, c₁, b₂, c₂) та­ко­вы, как ска­за­но в Утвер­жде­нии 1, и об­рат­но, каж­дая чет­вер­ка (b₁, c₁, b₂, c₂), удо­вле­тво­ря­ю­щая усло­вию Утвер­жде­ния 1, ровно одним спо­со­бом до­стра­и­ва­ет­ся до пары удо­вле­тво­ря­ю­щей усло­вию за­да­чи.

Утвер­жде­ние 2. Ко­ли­че­ство чет­ве­рок (b₁, c₁, b₂, c₂). Удо­вле­тво­ря­ю­щих усло­ви­ям пер­во­го утвер­жде­ния, есть в точ­но­сти План ре­ше­ния на­ме­чен, оста­лось его осу­ще­ствить.

Лемма 1. Вся­кое ин­те­рес­ное число имеет вид:

где и И об­рат­но, вся­кая за­пись та­ко­го вида яв­ля­ет­ся кор­рект­ной за­пи­сью в t-ичной си­сте­ме счис­ле­ния ин­те­рес­но­го числа.

До­ка­за­тель­ство. Усло­вие, что число яв­ля­ет­ся ин­те­рес­ным есть или эк­ви­ва­лент­но

Зна­чит, по за­дан­но­му зна­че­нию пара (a, d) вос­ста­нав­ли­ва­ет­ся не более чем одним спо­со­бом, иначе число имело бы боль­ше одной за­пи­си в t-ичной си­сте­ме счис­ле­ния. Но за­ме­тим, что при под­ста­нов­ке ра­вен­ство верно тож­де­ствен­но, кроме того, (за это от­ве­ча­ет усло­вие не­ра­вен­ства и оче­вид­но сле­ду­ют из

До­ка­за­тель­ство утвер­жде­ния 1. Пусть и   — два ин­те­рес­ных числа. Рас­смот­рим «t−ичную за­пись без пе­ре­но­сов»

же может и не быть пра­виль­ной t-ичной за­пи­сью, по­сколь­ку не­ко­то­рые из «цифр» могут быть боль­ше t; но она удо­вле­тво­ря­ет ра­вен­ству (*), по­сколь­ку ему удо­вле­тво­ря­ют и По­смот­рим, что про­ис­хо­дит, когда мы «вспо­ми­на­ем», что надо сде­лать пе­ре­нос. Если пе­ре­нос из раз­ря­да еди­ниц, то d умень­ша­ет­ся на t, а c уве­ли­чи­ва­ет­ся на 1 , зна­чит, всего левая часть (*) уве­ли­чи­ва­ет­ся на 1. Ана­ло­гич­но если пе­ре­нос из раз­ря­да t  — то c умень­ша­ет­ся на t и b уве­ли­чи­ва­ет­ся на 1, всего левая часть (*) уве­ли­чи­ва­ет­ся на Ана­ло­гич­но при пе­ре­но­се из раз­ря­да левая часть (*) умень­ша­ет­ся на За­ме­тим, что из од­но­го раз­ря­да не может быть сде­ла­но боль­ше од­но­го пе­ре­но­са: то что стоит в раз­ря­де есть сумма двух цифр, плюс воз­мож­но еди­нич­ка, при­шед­шая из пе­ре­но­са  — это точно мень­ше 2t. Зна­чит, если со­от­но­ше­ние (*) вы­пол­ня­лось до всех пе­ре­но­сов и вы­пол­ня­ет­ся после всех  — то либо не было сде­ла­но ни од­но­го пе­ре­но­са, либо были сде­ла­ны все три. До­ка­жем, что пер­вый ва­ри­ант не­воз­мо­жен.

В самом деле, по Лемме 1, ана­ло­гич­но Но если из раз­ря­да еди­ниц не было пе­ре­но­сов, из раз­ря­да его тоже не было (число оста­лось че­ты­рех­знач­ным), тогда сумма цифр в этих раз­ря­дах сей­час равна

Но такую сумму двумя циф­ра­ми можно на­брать един­ствен­ным об­ра­зом: То есть По Лемме 1 это озна­ча­ет

то есть   — тогда из раз­ря­да t₂ есть пе­ре­нос  — про­ти­во­ре­чие!

Итак, долж­ны осу­ще­ствить­ся ровно три пе­ре­но­са. До­ка­жем, что это эк­ви­ва­лент­но усло­вию В раз­ря­де еди­ниц стоит

при пе­ре­нос есть; в раз­ря­де t стоит (еди­нич­ка при­ш­ла от пе­ре­но­са)  — пе­ре­нос есть тогда и толь­ко тогда, когда в раз­ря­де стоит

при пе­ре­нос есть, на­ко­нец из раз­ря­да пе­ре­но­са нет когда он есть из раз­ря­да еди­ниц.

Для Утвер­жде­ния 2 мы при­ве­дем ком­би­на­тор­ное до­ка­за­тель­ство.

Ком­би­на­тор­ное до­ка­за­тель­ство Утвер­жде­ния 2 с на­во­дя­щи­ми со­об­ра­же­ни­я­ми. На­пом­ним, что вы­ра­же­ние счи­та­ет спо­со­бы рас­ста­вить в ряд n белых и k чер­ных шаров. На­учим­ся через такие функ­ции вы­ра­жать от­ве­ты в за­да­чах типа нашей, нач­нем с более про­стой.

По­учи­тель­ный при­мер 1. Пусть мы хотим пе­ре­чис­лить пары (c₁, c₂), такие что и По­стро­им для этого би­ек­цию между та­ки­ми па­ра­ми, и рас­ста­нов­ка­ми в ряд двух чер­ных и бе­ло­го ша­ри­ка сле­ду­ю­щим об­ра­зом: для рас­ста­нов­ки по­счи­та­ем число белых ша­ри­ков, сто­я­щих пра­вее ле­во­го чер­но­го ша­ри­ка (не важно до или после пра­во­го чер­но­го)  — на­зо­вем это число c₁; ана­ло­гич­но по­счи­та­ем число белых шаров, сто­я­щих левее пра­во­го чер­но­го  — на­зо­вем это число c₂. Оче­вид­но, оба числа лежат в за­ка­зан­ных пре­де­лах, при­том   — каж­дый белый шарик по­счи­тан хотя бы один раз, те что стоят между чер­ны­ми по­счи­та­ны два­жды. Остав­ля­ем чи­та­те­лю до­ду­мать, по­че­му по­стро­е­на имен­но би­ек­ция, то есть по паре (c₁, c₂) можно по­стро­ить рас­ста­нов­ку ша­ри­ков в ряд, при­том ровно одну. Итак, ко­ли­че­ство таких пар (c₁, c₂) есть в точ­но­сти

По­учи­тель­ный при­мер 2. От­лич­но, услож­ним за­да­чу. Пусть мы ищем число чет­ве­рок (b₁, c₁, b₂, c₂), таких что

и на­ко­нец Да­вай­те смот­реть на рас­ста­нов­ки в ряд че­ты­рех чер­ных шаров и бе­ло­го. Пер­вый чер­ный шар будет от­ве­чать за b₁, вто­рой за c₁, для каж­до­го из них со­от­вет­ству­ю­щи­ми чис­ла­ми мы будем на­зы­вать число белых шаров впра­во от них, тогда ав­то­ма­ти­че­ски по­лу­чит­ся, что (вся­кий белый шар, ко­то­рый пра­вее вто­ро­го слева чер­но­го, также пра­вее и пер­во­го слева чер­но­го). Ана­ло­гич­но тре­тий и чет­вер­тый чер­ные шары от­ве­ча­ют за числа c₁ и b₂ со­от­вет­ствен­но, при­чем числа равны Ко­ли­че­ству белых шаров левее со­от­вет­ству­ю­ще­го чер­но­го. Ана­ло­гич­но имеем а также пол­но­стью ана­ло­гич­но про­шло­му при­ме­ру. Итак, ко­ли­че­ство таких чет­ве­рок (b₁, c₁, b₂, c₂) есть в точ­но­сти

A те­перь соб­ствен­но то, что нам нужно. На­пом­ним: мы ищем число таких чет­ве­рок b₁, c₁, b₂, c₂, что

и на­ко­нец Чтобы дей­ство­вать как в при­ме­ре 2 нам нужно было бы пе­ре­счи­тать рас­ста­нов­ки в ряд 4 чер­ных и бе­ло­го шара, такие что между пер­вым и вто­рым чер­ны­ми стоят хотя бы два белых, и между тре­тьим и чет­вер­тым чер­ны­ми стоят хотя бы два белых. Сде­ла­ем это так: пе­ре­чис­лим все рас­ста­нов­ки в ряд че­ты­рех чер­ных и t − 5 белых, таких рас­ста­но­вок ровно

Те­перь в каж­дую из рас­ста­но­вок до­ба­вим два белых шара между пер­вым и вто­рым чер­ны­ми, и два белых между тре­тьим и чет­вер­тым чер­ны­ми. Остав­ля­ем чи­та­те­лю до­ка­зать, что по­стро­е­на би­ек­ция между мно­же­ством всех рас­ста­но­вок че­ты­рех чер­ных и t − 5 белых, и мно­же­ством рас­ста­но­вок с при­ве­ден­ным выше до­пол­ни­тель­ным усло­ви­ем че­ты­рех чер­ных и t − 1 бе­ло­го.

За­ме­тим, что воз­мож­но и чисто ал­геб­ра­и­че­ское до­ка­за­тель­ство утвер­жде­ния 2, ко­то­рое мы не при­во­дим по двум при­чи­нам: во-пер­вых, оно ничем не хо­ро­шо по срав­не­нию с ком­би­на­тор­ным, но тех­ни­че­ски су­ще­ствен­но слож­нее. Во-вто­рых, никто из участ­ни­ков, пы­тав­ших­ся прой­ти этим путем, к за­вер­ше­нию не по­до­шел даже близ­ко.

Ответ: