ЗАДАЧА ДЛЯ 5-7 КЛАССОВ! 98 БАЛЛОВ! Помогите решить, пожалуйста!!!
Можно из Интернета, из книги и из любого источника, но только с решением, пожалуйста! Решившему буду очень благодарна!
При каких n можно пометить вершины правильного n*(n+1)/2 - угольника числами от 1 до n (а) и от 0 до n (б) так, чтобы для каждой пары различных натуральных чисел, не превосходящих n нашлась сторона, концы которой помечены этими числами? (Условие вверху дословно)
То есть у вас есть плоский многоугольник с n*(n+1)/2 вершинами, и спрашивается, при каких n в его вершинах можно расставить числа от 1 до n от 0 до n, так, чтобы для каждой пары нашелся отрезок, сторона, в вершинах которой стоят эти числа.
Можно из Интернета, из книги и из любого источника, но только с решением, пожалуйста! Решившему буду очень благодарна!
При каких n можно пометить вершины правильного n*(n+1)/2 - угольника числами от 1 до n (а) и от 0 до n (б) так, чтобы для каждой пары различных натуральных чисел, не превосходящих n нашлась сторона, концы которой помечены этими числами? (Условие вверху дословно)
То есть у вас есть плоский многоугольник с n*(n+1)/2 вершинами, и спрашивается, при каких n в его вершинах можно расставить числа от 1 до n от 0 до n, так, чтобы для каждой пары нашелся отрезок, сторона, в вершинах которой стоят эти числа.
More Questions From This User See All
Answers & Comments
(б)
Пусть n - нечётное. Докажем, что тогда условие задачи невыполнимо. Всего пар соседних чисел в многоугольнике столько же, сколько и чисел. Так как многоугольник, удовлетворяющий условиям задачи, содержит все возможные пары хотя бы по одному разу, а различных пар ровно n*(n+1)/2, то каждая пара соседних различных чисел встречается в многоугольнике ровно один раз. Но если n нечётно, то число "0" участвует в нечётном количестве пар, но тогда либо не будет хотя бы одной пары, либо хотя бы одна пара появится дважды. Значит, n - чётное число.
Пусть n - чётное. Будем строить пример по индукции.
База (n = 2): >-0-1-2-> (и так сойдёт).
Переход (от n = 2k-2 к n = 2k):
Пусть мы умеем строить пример для n = 2k-2. Найдём место, где стоят рядом числа "0" и "1" и "увеличим" многоугольник в этом месте, добавив между ними 2n - 1 пустую вершину (теперь из (n-2)*(n-1)/2-угольника мы получили n*(n+1)/2-угольник). Рядом с числом "1" напишем число "0" (повторения не будет, так как теперь исходные "0" и "1" стоят отдельно). Осталось 2n - 2 пустые вершины. Теперь мы должны получить такую цепь ("2k" и "2k-1" чередуются (через 1 число), p и q - они же, но мы не знаем (не хотим перебирать два случая), в каком порядке они стоят около "k", так что считаем, что "слева" стоит p. Все числа кроме "2k" и "2k-1" - последовательные числа от "1" до "2k-2"):
(???)--0--(2k)--(1)--(2k-1)--(2)--(2k)--(3)--...(p)--(k)--(q)--(p)--(k+1)--(q)--...--(2k)--(2k-2)--(2k-1)--(0)--(1)--(???)
Заметим, что все числа (кроме 2k, 2k-1 и пары "0-1") остались на своих местах, следовательно, все пары сохранились. Пару 0-1, а также все пары для чисел "2k" и "2k-1" (каждое из них стоит рядом с каждым из остальных чисел, а также они стоят рядом друг с другом), мы сделали. Следовательно, пример верен и переход индукции завершён.
(а)
Для n = 1 пример очевиден.
Для n = 2k, заменим все числа "0" на "1" в примере для 2k из задачи "б". Все требуемые пары всё ещё останутся.
Для n = 2k + 1, построим пример для n = 2k, между "0" и "1" добавим n + 1 нуль (чтобы достичь нужного количества чисел в многоугольнике), а потом увеличим все числа на 1. Все требуемые пары сохранятся.
Ответ: (а) при любых n; (б) при чётных n.