а)  За­ме­тим, что все сла­га­е­мые в по­лу­чен­ной сумме де­лят­ся на 9, кроме того сла­га­е­мо­го, ко­то­рое со­дер­жит трой­ку из вто­ро­го на­бо­ра. Зна­чит, и вся сумма не де­лит­ся на 9.

б)  Может. Пусть, на­при­мер, пе­ре­мно­жи­ли мак­си­маль­ные числа из пер­во­го и вто­ро­го на­бо­ра, а осталь­ные пары сфор­ми­ро­ва­ли про­из­воль­ным об­ра­зом. За­ме­тим, что Таким об­ра­зом, уже одно из сла­га­е­мых по­лу­чен­ной суммы боль­ше, чем мил­ли­он, зна­чит, и вся сумма тем более боль­ше, чем мил­ли­он.

в)  Наи­мень­шее зна­че­ние суммы до­сти­га­ет­ся, если умно­жить наи­боль­шее число из вто­ро­го на­бо­ра на наи­мень­шее из пер­во­го, вто­рое по ве­ли­чи­не число из вто­ро­го на­бо­ра умно­жить на сле­ду­ю­щее за наи­мень­шим чис­лом из пер­во­го и т. д., а по­лу­чен­ные про­из­ве­де­ния сло­жить. Таким об­ра­зом, наи­мень­шая воз­мож­ная сумма равна

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

Будем про­дол­жать, пока мно­жи­тель не пе­рейдёт в пер­вое сла­га­е­мое Затем по­сту­пим так же с мно­жи­те­лем   — он пе­рей­дет во вто­рое сла­га­е­мое и т. д. Ука­зан­ным об­ра­зом пре­об­ра­зу­ем ис­ход­ную сумму в наи­мень­шую воз­мож­ную сумму

Ответ: а) нет; б) да; в)

При­ме­ча­ние Дмит­рия Му­хи­на (Москва).

Под­го­тов­лен­ный чи­та­тель уви­дит в за­да­че пе­ре­ста­но­воч­ное не­ра­вен­ство, на­зы­ва­е­мое также транс­не­ра­вен­ством. При­ве­дем и до­ка­жем его.

Тео­ре­ма. Пусть   — какая-⁠то пе­ре­ста­нов­ка чисел 1, 2, 3, ..., n. Тогда

До­ка­за­тель­ство. При­ме­ним метод ма­те­ма­ти­че­ской ин­дук­ции. Про­ве­рим базу ин­дук­ции: если а то

По­лу­чен­ное не­ра­вен­ство верно, по­сколь­ку мно­жи­те­ли имеют раз­ные знаки.

Ин­дук­ци­он­ный пе­ре­ход: пред­по­ло­жим, что утвер­жде­ние верно при до­ка­жем, что тогда оно верно и при Если то не­ра­вен­ство сво­дит­ся к пред­по­ло­же­нию ин­дук­ции. Если то по­ме­ня­ем эти мно­жи­те­ли ме­ста­ми:

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

Таким об­ра­зом, по прин­ци­пу ма­те­ма­ти­че­ской ин­дук­ции, не­ра­вен­ство (1) до­ка­за­но. Ана­ло­гич­но до­ка­зы­ва­ет­ся не­ра­вен­ство (2).