Uzdevums

LV.NOL.2023.11.5 en lv

Skaitļu virkni, kurā ir \(N\) elementi, sauksim par \(N\) mazāko naturālo skaitļu permutāciju, ja tajā atrodami visi naturālie skaitļi no \(1\) līdz \(N\).

Zināms, ka virkne \(\left\{ a_{i} \right\}\) ir \(n\) (\(n>3\)) mazāko naturālo skaitļu permutācija.

Virknes \(\left\{ b_{i} \right\}\) (\(1 \leq i \leq n-1\)) elementus aprēķina pēc formulas \(b_{i}=\left|a_{i+1}-a_{i}\right|\).

Virknes \(\left\{ c_{i} \right\}\) (\(1 \leq i \leq n-2\)) elementus aprēķina pēc formulas \(c_{i}=\left|b_{i+1}-b_{i}\right|\).

Pierādīt, ka \(\left\{ b_{i} \right\}\) un \(\left\{ c_{i} \right\}\) vienlaikus abas nevar būt attiecīgi \(n-1\) un \(n-2\) mazāko naturālo skaitļu permutācijas!

Hide solution

en lv

Solution

Assume the contrary, that both sequences \(\left\{b_{i}\right\}\) and \(\left\{c_{i}\right\}\) are permutations of the \(n-1\) and \(n-2\) smallest numbers, respectively. This means that the sequence \(\left\{c_{i}\right\}\) contains the number \(n-2\), while the sequence \(\left\{b_{i}\right\}\) contains all numbers from \(1\) to \(n-1\).

For clarity, write the sequences one under the other so that the element \(b_{i}\) is placed below and between the elements \(a_{i}\) and \(a_{i+1}\), and the element \(c_{i}\) is placed below and between \(b_{i}\) and \(b_{i+1}\). Directly above \(n-2\) in the sequence \(\left\{c_{i}\right\}\) there must be the numbers \(1\) and \(n-1\) from the sequence \(\left\{b_{i}\right\}\), since there is no other way to obtain \(n-2\) in \(\left\{c_{i}\right\}\). Similarly, directly above \(n-1\) in the sequence \(\left\{b_{i}\right\}\) there must be the numbers \(1\) and \(n\) from the sequence \(\left\{a_{i}\right\}\), since there is no other way to obtain the number \(n-1\) in \(\left\{b_{i}\right\}\). Thus there are two possibilities for which numbers are in the sequence \(\left\{a_{i}\right\}\) above \(1\) and \(n-1\) (see Figs. 11 and 12). The cases where the numbers \(1\) and \(n-1\) in the sequence \(\left\{b_{i}\right\}\) appear in the opposite order are symmetric to these.

In the sequence \(\left\{b_{i}\right\}\) the number \(n-2\) must also appear somewhere, which can be obtained only in two ways: either as \(n-2\), or as \((n-1)-1\). Therefore, in the sequence \(\left\{a_{i}\right\}\) either the pair of numbers \((1;n-1)\) or \((2;n)\) must be adjacent. But in neither case is this possible. Indeed, in the case of Fig. 11, \(1\) and \(n-1\) are not adjacent, while both neighbors of \(n\) are already occupied; similarly, in the case of Fig. 12, the numbers \(2\) and \(n\) are not adjacent, while both neighbors of \(1\) are already occupied. Thus the assumption was false, and the sequences \(\left\{b_{i}\right\}\) and \(\left\{c_{i}\right\}\) cannot simultaneously be permutations of the \(n-1\) and \(n-2\) smallest natural numbers.

Atrisinājums

Pieņemsim pretējo, ka abas virknes \(\left\{b_{i}\right\}\) un \(\left\{c_{i}\right\}\) ir attiecīgi \(n-1\) un \(n-2\) mazāko skaitļu permutācijas. Tas nozīmē, ka virknē \(\left\{c_{i}\right\}\) ir skaitlis \(n-2\), bet virknē \(\left\{b_{i}\right\}\) ir visi skaitļi no \(1\) līdz \(n-1\).

Uzskatāmības pēc rakstīsim virknes vienu zem otras tā, ka elements \(b_{i}\) atrodas zem elementiem \(a_{i}\) un \(a_{i+1}\) pa vidu un arī elements \(c_{i}\) atrodas zem elementiem \(b_{i}\) un \(b_{i+1}\) pa vidu. Tieši virs \(n-2\) virknē \(\left\{c_{i}\right\}\) jāatrodas virknes \(\left\{b_{i}\right\}\) skaitliem 1 un \(n-1\), jo nav cita veida, kā virknē \(\left\{c_{i}\right\}\) iegūt \(n-2\). Līdzīgi tieši virs \(n-1\) virknē \(\left\{b_{i}\right\}\) jāatrodas virknes \(\left\{a_{i}\right\}\) skaitļiem \(1\) un \(n\), jo nav cita veida, kā virknē \(\left\{b_{i}\right\}\) iegūt skaitli \(n-1\). Tādējādi ir iespējami divi varianti, kādi skaitḷi atrodas virknē \(\left\{a_{i}\right\}\) virs \(1\) un \(n-1\) (skat. 11. att. un 12. att.). Gadījumi, kad virknē \(\left\{b_{i}\right\}\) skaitļi \(1\) un \(n-1\) atrodas pretējā secībā, ir šiem simetriski.

Virknē \(\left\{b_{i}\right\}\) kaut kur jāatrodas arī skaitlim \(n-2\), ko var iegūt tikai divos veidos: vai nu kā \(n-2\), vai arī kā \((n-1)-1\). Tātad virknē \(\left\{a_{i}\right\}\) vai nu skaitļu pārim \((1 ; n-1)\), vai arī \((2 ; n)\) jāatrodas blakus. Bet nevienā no gadījumiem tas nav iespējams. Patiešām, 11.att. gadijumā \(1\) un \(n-1\) neatrodas blakus, bet skaitlim \(n\) abi kaimiņi jau ir aizņemti, un līdzīgi 12.att. gadijumā skaitḷi \(2\) un \(n\) neatrodas blakus, bet skaitlim \(1\) abi kaimiņi jau ir aizņemti. Tātad pieņēmums bija aplams un abas virknes \(\left\{b_{i}\right\}\) un \(\left\{c_{i}\right\}\) vienlaikus nevar būt attiecīgi \(n-1\) un \(n-2\) mazāko naturālo skaitļu permutācijas.