Пусть М — некоторое множество пар натуральных чисел (i, j), для фиксированного При этом, если пара (i, j) принадлежит М, то никакая пара (j, k) ему не принадлежит. Какое наибольшее множество пар может быть во множестве М?
Назовём натуральное число k из интервала от 1 до n начальным, если оно является меньшим числом в некоторой паре из M, а натуральное число l из интервала от 1 до n конечным, если оно является большим числом в некоторой паре из М. Никакое число m из интервала от 1 до n не может являться одновременно и начальным и конечным, в противном случае М содержало бы одновременно пары и для некоторых i и j, что невозможно по условию. Каждая пара из М полностью определяется своими начальным числом i и конечным число j, следовательно, М содержит не более ab пар, где a и b количества его начальных и конечных чисел соответственно. Тогда — квадратичная функция от целого переменного a. При чётном n она принимает максимальное значение при а при нечётном n она принимает максимальное значение при и
Пример множества М, для которого эти максимальные оценки достигаются, строится так: объявим начальными все числа от 1 до при чётном n, и все числа от 1 до при нечётном n, остальные числа объявим конечными. Поместим в М все возможные пары начального и конечного чисел. Их будет как раз столько, сколько в ответе.
Ответ: при четном n, при нечетном n.