УПОРЯДКОВАНІ НАБОРИ ЧИСЕЛ

УПОРЯДКОВАНІ НАБОРИ ЧИСЕЛ

Одна властивість упорядкованих наборів

Почнемо з цікавої нерівності.

Задача 1. Довести, що для будь-яких додатних чисел а, b, с спра­ведливі співвідношення

a∙2^-a + b∙2^-b + с∙2^-c £  (b+c)∙2^-a-1 + (a+c)∙2^-b-1 + (b+a)∙2^-c-1£

£ a∙2^a-b-c + b∙2^b-a-c + с∙2^c-a-b        (1.1)

Один з можливих підходів до розв'язування полягає в наступно­му.

Розглянемо дві трійки додатних чисел:

x₁ ,х₂, х₃;              y₁ ,y ₂, y₃;  

Вважатимемо, що обидві трійки упорядковані за зростанням, тобто

x₁ £ х₂ £ х₃;             y₁ £y ₂ £ y₃; 

Утворимо суму

S = х₁у_і + х₂у_j + х₃y_к.

Тут і, j, k – номери 1, 2, 3, записані в довільному порядку.

Як ви­брати цей порядок так, щоб сума S виявилася найбільшою (наймен­шою) з можливих?

Виявляється (нижче це буде строго доведено), що сума буде більшою, якщо більші числа множити на більші, а менші на менші.

Також сума буде меншою, якщо більші числа множити на менші, а менші на більші.

Іншими словами, справедлива нерівність

х₁у₃+х₂у₂+х₃y₁ £ S £  х₁у₁+х₂у₂+х₃y₃.                        (1.2)

Розв'язання задачі 1

Доведемо спочатку першу з нерівностей (1.1). Запишемо дві трійки

чисел, вважаючи

а £  b £  с,

 а  тому

2^-c  £  2^-b  £  2^-a

а,   b,   с;

2^-a  ,  2^-b  , 2^-c.

 Ми розмістили найбільше з чисел першої трійки над найменшим із чисел другої трійки, найменше з чисел першої трійки розташова­но над найбільшим із чисел другої трійки. З нерівності (1.2) випли­вають співвідношення:

a∙2^-a + b∙2^-b + с∙2^-c £  a∙2^-b + b∙2^-c + c∙2^-a,

a∙2^-a + b∙2^-b + с∙2^-c £ a∙2 ^-c + b∙2^-a + с∙2^-b.

Додаючи ці нерівності, одержуємо

2∙(a∙2^-a + b∙2^-b + с∙2^-c ) £  (b+c)∙2^-a + (a+c)∙2^-b + (b+a)∙2^-c.

Для доведення другої з нерівностей (1.1) розглянемо трійки чисел:

a∙2^a ,   b∙2^b ,   с∙2^c ;

2^a ,  2^b , 2^c ;

Оскільки

0 < а  £  b £  с,

то

2^a  £    2^b  £   2^c

і

a∙2^a   £     b∙2^b   £     с∙2^c.

Тому з нерівності (1.2) випливає

a∙2^a+b + b∙2^b+c + с∙2^a+c £  a∙2^2a + b∙2^2b + с∙2^2c,

a∙2^a+c + b∙2^b+a + с∙2^b+c £  a∙2^2a + b∙2^2b + с∙2^2c.

Додаючи ці нерівності, маємо

(a+b)∙2^a+c + (b+c)∙2^b+c + (a+с)∙2^a+c £  2(a∙2^2a + b∙2^2b + с∙2^2c) . (1.3)

Помноживши обидві частини нерівності (1.3) на 2^-a-b-c  одержи­мо шукане співвідношення.

У розв'язанні задачі 1 особливу роль відіграли впорядковані трійки чисел. Розглянемо тепер набори з n чисел. Числам у наборах присвоєно номери

1, 2,..., n.

Означення. Набір чисел а,, а₂,..., а_n називається упорядкованим за зростанням, якщо для кожного k:

1 £  k £ n-1,

має місце нерівність

а_к £  а_k+1,

 і називається упорядкованим за спаданням, якщо з нерівності

1 £  k £ n-1,

випливає співвідношення

а_к+1 £ а_k .

Набір чисел, упорядкова­ний або за зростанням, або за спаданням, називається упорядкованим.

Іншими словами, упорядкованість за зростанням даних чисел збе­рігає порядок, тобто більшим індексам відповідають більші числа.

Упорядкованість за спаданням змінює порядок на протилежний:

більшим індексам відповідають менші числа.

Теорема. Набір чисел {а_k, 1£ k £ n } упорядкований тоді і тільки тоді, коли

|а₁ -а₂|+...|а_n-1 -а_n|  = |а₁ –а_n|.

Довести самостійно.

Дамо геометричне тлумачення:   абсолютна величина чисел а_k,

|a₁|£ |а_k| £ |a_n|.

Перейдемо тепер до доведення нерівності (1.2), точніше, до її уза­гальнення.

Теорема 1. Нехай дано два упорядкованих за зростанням набори чисел:

а₁  £ а₂   £ ...  £  а_n-1  £   а_n ;   

b₁  £ b ₂   £ ...  £  b _n-1  £   b _n    

Для довільної перестановки

i(1), i(2),..., i(n)

чисел

1, 2,..., n

і відпо­відної суми

S = а₁b _i(1) + а₂ b_{i(2 )} + ...  + а_n-1 b_i(n-1)  + а_nb _i(n)

виконуються нерівності

а₁b_n  + а₂ b_n-1    + ...  +  а_n-1 b₂   +   а_nb₁  £   S £ а₁b₁  + а₂ b₂    + ...  +  а_n-1 b_n-1   +   а_nb_n. (*)   

Доведення. Доведемо справедливість тільки другої з нерівностей (1.4) (першу доведіть самостійно).

Перевіримо спочатку виконання нерівності (*) якщо n = 2. Не­тотожна перестановка чисел 1, 2 є перестановкою i(1) = 2, i(2) =1,  1 вираз (1.4) перетворюється у і нерівність

а₁b₂  + а₂ b₁     £   а₁b₁  + а₂ b₂            (1.5)

яка рівносильна очевидній нерівності

0 £ (а₂ –а₁ )(b₂ -b₁).

Тепер нескладно довести наше твердження для довільного  n. Справді, нехай сума S  містить доданки

а_jb_i,   та          а_mb_k ,

для яких

j < m,  i  > k

і, отже,

b_i   >=  b_{k .}

Поміняємо місцями числа

b_i   та   b_k  .

Згідно з нерівністю (1.5) одержимо суму   

S^’ >= S

з доданками

а_jb_k,   та          а_mb_i ,

По­слідовно виконуючи такі перестановки, через скінченну кількість кроків прийдемо до суми

а₁b₁  + а₂ b₂    + ...  +  а_n-1 b_n-1   +   а_nb_n.

Тому

S^’  £ а₁b₁  + а₂ b₂    + ...  +  а_n-1 b_n-1   +   а_nb_n.

Завдання 3. Оцінити, скільки кроків достатньо, щоб суму S^’  пере­творити в S.

Завдання 4. Чи не можна послабити вимогу додатності чисел а, b, с у задачі 1?

Завдання 5. Коли в одній з нерівностей (1.4) можлива рівність?

Теорема  дає можливість доводити багато цікавих нерівностей. Докладніше про це див. у статті Л.Пінтера, И.Хегедиша «Упорядоченные наборы чисел и неравенства» («Квант», 1985, № 12).

Нерівність Чебишова

Зупинимося на одному із застосувань доведеної теореми. Розгля­
немо два упорядкованих за зростанням набори:

а₁  £ а₂   £ ...  £  а_n-1  £   а_n ;   

b₁  £ b ₂   £ ...  £  b _n-1  £   b _n .   

Теорема 1. Справедливим є співвідношення

(а₁ + а₂  + ...+ а_n-1 + а_n)(b₁ +b₂ +...+ b_n-1 +b_n) £ n(а₁b₁ + а₂ b₂  + ...+ а_n-1 b_n-1 + а_nb_n)_. (2.1)

Доведення

Попередня  теорема стверджує,  що

S = а₁b₁  + а₂ b₂    + ...  +  а_n-1 b_n-1   +   а_nb_n  >= а₁b _i(1) + а₂ b_{i(2 )} + ...  + а_n-1 b_i(n-1)  + а_nb_i(n)

Послідовно перебираючи перестановки

i(1), i(2),..., i(n)

одержує­мо n нерівностей:

а₁b₁  + а₂ b₂    + ...  +  а_n-1 b_n-1   +   а_nb_n  £ S,

а₁b₂  + а₂ b₃    + ...  +  а_n-1 b_n+   а_nb₁  £ S ,

а₁b₃  + а₂ b₄    + ...  +  а_n-1 b₁   +   а_nb₂  £ S ,

…………………………………………….

а₁b_n  + а₂ b₁    + ...  +  а_n-1 b_n-1   +   а_nb_n-1  £ S .

Додамо їх і отримаємо

а₁(b₁ +b₂ +...+ b_n-1 +b_n)+

а₂(b₁ +b₂ +...+ b_n-1 +b_n) +

...

+ а_n(b₁ +b₂ +...+ b_n-1 +b_n) =

= (а₁ + а₂  + ...+ а_n-1 + а_n)(b₁ +b₂ +...+ b_n-1 +b_n) £ nS.

Цю нерівність називають нерівністю Чебишо­ва – за ім'ям видатного російського математика і механіка, засновника петербурзької математич­ної школи Пафнутія Львовича Чебишова (1812–1894). Основні його праці стосуються математич­ного аналізу, теорії наближення функцій поліно­мами, теорії чисел, теорії ймовірностей, теорії машин і механізмів.

Завдання 1. Довести, що у нерівності Чебишо­ва рівність досягається тоді і тільки тоді, коли або всі а_k або всі b_і  рівні між собою.