а)  За­пи­шем усло­вие в виде

и пре­об­ра­зу­ем его Ясно, что Кроме того, от­ку­да и В то же время от­ку­да Итак, Урав­не­ние сво­дит­ся к Ясно, что (при по­лу­чи­лось бы чет­ное зна­че­ние), а тогда и Ответ

б)  Ясно, что мак­си­маль­ное зна­че­ние n до­сти­га­ет­ся при До­ка­жем, что оно равно по ин­дук­ции. База   — вер­ное утвер­жде­ние.

Пе­ре­ход. Пусть тогда

что и тре­бо­ва­лось до­ка­зать.

в)  Ясно, что каж­до­му на­бо­ру t_i (ко­то­рых ровно по­сколь­ку вы­брать t_i можно спо­со­бом не­за­ви­си­мо от дру­гих вы­бо­ров) со­от­вет­ству­ет ровно одно целое число, при­чем оно все­гда от 0 до (см. пункт б). В этом про­ме­жут­ке как раз целых чисел. Оста­лось до­ка­зать, что ни­ка­кие два зна­че­ния N для раз­ных на­бо­ров не сов­па­да­ют. До­пу­стим, они сов­па­ли. Вы­бе­рем мак­си­маль­ный ин­декс i для ко­то­ро­го в пер­вом на­бо­ре t_i от­ли­ча­ет­ся от p_i во вто­ром на­бо­ре. Пусть в пер­вом оно боль­ше.

Тогда уже за счет сла­га­е­мо­го вме­сто сумма в пер­вом на­бо­ре боль­ше суммы во вто­ром на­бо­ре ми­ни­мум на Все боль­шие сла­га­е­мые в сум­мах равны, а мень­шие, даже если во вто­ром на­бо­ре взять мак­си­маль­но воз­мож­ные ко­эф­фи­ци­ен­ты, а в пер­вом нули, ском­пен­си­ру­ют лишь раз­ни­цу

и сумма в пер­вом на­бо­ре оста­нет­ся боль­ше. Итак, суммы не могут сов­пасть. Зна­чит, каж­дая по­тен­ци­аль­но воз­мож­ная сумма по­лу­ча­ет­ся ровно один раз.

г)  Сна­ча­ла най­дем набор такой, что

По до­ка­зан­но­му выше, можно ис­кать числа с конца, вы­би­рая мак­си­маль­но воз­мож­ное t_i, для ко­то­ро­го сумма еще не пре­вос­хо­дит нуж­ной (если вы­брать боль­ше, то сумма будет боль­ше чем надо, а если мень­ше, то даже мак­си­маль­но воз­мож­ные мень­шие сла­га­е­мые не смо­гут этого ском­пен­си­ро­вать).

По­лу­ча­ем по­сле­до­ва­тель­но, при

Те­перь можно уста­но­вить место каж­до­го из чисел в пе­ре­ста­нов­ке. На­при­мер, 1 долж­на сто­ять после 0 (иначе ). Те­перь по­ста­вим двой­ку. Она долж­на сто­ять левее и 1 и 0, чтобы вы­пол­ня­лось Ана­ло­гич­но до­бав­ля­ем осталь­ные числа. По­сле­до­ва­тель­но по­лу­чим

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

Ответ: а) 1; 2; 0; г) 2, 5, 4, 0, 6, 3, 1.