4
2

Пусть $%n\geq3$% — целое число. Рассмотрим окружность и $%n + 1$% точек на ней, разбивающих её на равные дуги. Рассмотрим все способы пометить эти точки числами $%0, 1, . . . , n$% так, что каждое число использовано ровно один раз. Два способа, отличающихся поворотом, считаются одинаковыми. Способ пометки называется красивым, если для любых четырех меток $%a < b < c < d$% таких, что $%a + d = b + c$%, хорда, соединяющая точки с метками $%a$% и $%d$%, не пересекает хорду, соединяющую точки с метками $%b$% и $%c$%.
Пусть $%M$% — количество красивых способов пометки. Пусть $%N$% — количество упорядоченных пар $%(x, y)$% натуральных чисел, удовлетворяющих условиям $%x + y \leq n$% и НОД$%(x, y) = 1$%.
Докажите, что $%M=N+1$%.

задан 14 Апр '14 0:23

изменен 15 Апр '14 18:35

Очень интересная задача, я сегодня попытался ее решить, много времени ушло, но не осилил. Может @falcao сможет ее решить?

(15 Апр '14 0:28) ratchet

@ratchet: я над ней думал, пытаясь установить связь между парами и способами расстановки чисел на основе наблюдений. Но пока закономерность как следует не уловил. Задача действительно интересная -- я собираюсь ещё подумать.

(15 Апр '14 0:31) falcao

@ratchet,@falcao: я тоже над ней думал, но не очень долго, но она сразу мне показалась интересной, поэтому решил поделиться с другими, завтра попробую более тщательно в нее вникнуть, может быть, что-нибудь получится.

(15 Апр '14 0:52) kirill1771

Я вспомнил, я видел эту задачу на какой-то (по моему, на международной) олимпиаде по математике, Вы ведь ее оттуда взяли.

(15 Апр '14 22:53) ratchet

@ratchet: да, это с международной олимпиады прошлого года.

(15 Апр '14 22:55) kirill1771

@kirill1771: я сегодня немного подумал над этой задачей, и, судя по всему, нашёл к ней "ключ", то есть способ решения, который должен сработать. Хочу всё проверить и додумать до конца. Если всё получится, то помещу решение.

(15 Апр '14 23:34) falcao

@falcao: ладно, я тоже думал, но пока особо не продвинулся. Интересно будет Ваше решение посмотреть, если получится все.

(15 Апр '14 23:36) kirill1771
1

@kirill1771: я сегодня начал писать решение -- оно получилось очень длинное, потому что задача объективно сложная. В ней есть много чего описывать и проверять. Значительную часть я уже написал, но до конца не удалось завершить, а сейчас уже поздновато. Поэтому я надеюсь завтра закончить.

(17 Апр '14 1:39) falcao

@kirill1771: я сейчас помещу то, что написал вчера. Там текст пока не окончен: не хватает завершающего рассуждения. Но я уже продумал, как оно выглядит. Поэтому допишу с работы (я сейчас туда как раз отправляюсь).

(17 Апр '14 9:29) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
8

Прежде всего, выясним "природу" ответа к задаче. Поскольку там речь идёт о количестве пар взаимно простых чисел, естественно привлечь для описания функцию Эйлера $%\varphi$%. Очевидно, что числа $%x$% и $%y$% взаимно просты тогда и только тогда, когда это же верно для чисел $%x$% и $%x+y$%. Придавая сумме $%x+y=k$% значения от $%k=2$% до $%k=n$%, приходим к тому, что выбор натурального числа $%x$%, в пределах от $%1$% до $%k-1$%, взаимно простого с $%k$%, можно осуществить $%\varphi(k)$% способами. Поэтому $%N$% равно сумме чисел вида $%\varphi(k)$% по всем $%k$% от $%2$% до $%n$%. Нас интересует число, на единицу большее, и его естественно представить в виде $%\varphi(1)+\varphi(2)+\cdots+\varphi(n)$%. Именно про это число требуется доказать, что оно равно количеству красивых расстановок.

Анализ таких расстановок для небольших значений $%n$% показывает, что они устроены следующим образом. По обе стороны от нуля стоят различные числа $%a$%, $%b$%, принимающие значения от $%1$% до $%n$%. Очевидным необходимым условием существования красивого разбиения с этим свойством является неравенство $%a+b > n$%. В противном случае число $%a+b$%, отличное и от $%a$%, и от $%b$%, заведомо встречаются в расстановке, и тогда хорда, соединяющая $%0$% с $%a+b$%, пересекается с хордой, соединяющей $%a$% с $%b$%. Это противоречит определению красивой расстановки.

Помимо этого, для проанализированных значений $%n$% выполнено условие, что числа $%a$% и $%b$%, соседствующие с нулём, взаимно просты. Это наводит на мысль, что красивая расстановка именно этой парой чисел и "управляется". Возникает следующая гипотеза:

красивых расстановок столько же, сколько имеется упорядоченных пар вида $%(a;b)$%, где $%a$%, $%b$% -- различные взаимно простые натуральные числа в пределах от $%1$% до $%n$%, удовлетворяющие неравенству $%a+b\ge n+1$%.

Это предположение возникло почти сразу в ходе анализа, но далее я пытался найти "естественное" соответствие между парами $%x$%, $%y$% из условия и парами $%a$%, $%b$% из формулировки гипотезы. Это всё время не удавалось сделать, и тогда появилась идея, что достаточно просто осуществить подсчёт. Проверим это, доказывая тем самым, что из гипотезы следует требуемый вывод.

Прежде всего, можно снять условие $%a\ne b$%, потому что равные числа не могут быть взаимно простыми за исключением случая $%a=b=1$%, который не может иметь места ввиду $%a+b\ge n+1\ge4$%. Фиксируя значение $%a$% от $%1$% до $%n$%, мы отбираем взаимно простые с ним числа $%b$%, удовлетворяющие неравенству $%n+1-a\le b\le n$%. Это последовательные натуральные числа, которых имеется ровно $%a$%, и они будут взаимно просты с $%a$% тогда и только тогда, когда этим свойством обладают их остатки от деления на $%a$%. Но остатки принимают по разу все значения от $%0$% до $%a-1$%, и среди них имеется ровно $%\varphi(a)$% взаимно простых с $%a$% по определению функции Эйлера. В итоге получается, что подсчитываемое нами количество пар равно сумме $%\varphi(1)+\varphi(2)+\cdots+\varphi(n)$%, как и ожидалось.

Таким образом, всё сводится к доказательству гипотезы, сформулированной выше.

Рассмотрим произвольную расстановку, в которой после $%0$% (при движении по часовой стрелке, что далее всегда будет подразумеваться) стоит число $%a$%, и до $%0$% стоит $%b$%. Из соображений симметрии, можно считать, что $%a < b$%. Также мы будем предполагать, что $%a+b\ge n+1$%. Целью является проверка того, что если $%a$% и $%b$% не взаимно просты, то рассматриваемая расстановка не будет красивой. А если они взаимно просты, то красивая расстановка имеется, причём только одна.

Установим простое свойство, касающееся того, в каком порядке могут стоять на окружности числа $%x$% и $%y$% для тех случаев, когда модуль их разности принимает одно из значений $%a$%, $%b$% или $%b-a$%. В первом случае надо соединить числа $%x$% и $%y$% хордами с числами $%0$% и $%a$%соответственно. Если эти хорды пересекаются, что для красивой расстановки невозможен случай $%x=y+a$%. В предположении $%|x-y|=a$% это означает, что $%y-x=a$%. Вывод из этого следует такой: из чисел вида $%x+a$% и $%x$%, при чтении по часовой стрелке, сначала должно идти $%x$%, и только потом $%x+a$%. Заметим, что это верно и для пары $%0$%, $%a$%.

Рассматривая случай пары с условием $%|x-y|=b$%, мы таким же точно способом приходим к выводу, что в красивой расстановке число вида $%x+b$% всегда предшествует числу $%x$%, а для условия $%|x-y|=b-a$%, число вида $%x+(b-a)$% следует раньше, чем $%x$% (в заданном порядке прочтения). Эти условия являются весьма "жёсткими" и налагают сильные ограничения. Для удобства, представим эти правила символически в виде $%x\prec x+a$%; $%x+b\prec x$%; $%x+(b-a)\prec x$%, где $%\prec$% означает "встречается раньше при чтении по часовой стрелке без прохода "мимо" нуля". Самое последнее из правил имеет исключение: для $%x=a$% оно не имеет места. Запомнить суть этих правил легко, глядя на порядок следования чисел $%b$%, $%0$%, $%a$%.

Для наглядности, продемонстрируем на примере, к чему приводит применение этих правил при $%n=11$%, $%a=7$%, $%b=10$%. Единственный возможный порядок следования, в силу указанных правил, может быть только такой: 0, 7, 4, 11, 1, 8, 5, 2, 9, 6, 3, 10. Здесь при переходе от предыдущего числа к следующему мы используем одну из операций: "вычесть b-a=3", прибавить a=7", "вычесть b=10", причём это же имеет место при переходе от последнего числа к первому. Из сказанного пока не очевидно, будет ли эта расстановка красивой, но при этом понятно, что только она может претендовать на эту роль, если 0 окружён числами из рассматриваемого примера.

Проследим закономерность, по которой происходит переход от числа к следующему за ним числу в рассмотренном примере. Видно, что мы всегда прибавляем $%a$%, если это можно сделать (то есть $%x+a\le n$%). Заметим также, что в этом случае $%x\le n-a < b$%, и мы при этом не имеем возможности вычесть $%b$%. Если же мы имеем такую возможность (при $%x\ge b$%), то мы это число вычитаем. А если такой возможности нет, то мы вычитаем $%b-a$%, что всегда возможно, поскольку при $%x < b-a$% мы имели бы возможность прибавить $%a$%.

Описанный выше порядок действий относится к частному примеру, но если мы его применим к общей ситуации, то окажется, что числа должны располагаться по кругу именно в этом порядке -- пусть и не последовательно друг за другом. Имеется в виду, что если к числу $%x$% применить описанный выше процесс, то получится число $%f(x)$%, которое расположено после $%x$% при чтении по часовой стрелке, не проходя при этом через $%0$% -- пусть и не сразу вслед за ним. Отсюда легко вывести тот факт, что если $%a$%, $%b$% имеют нетривиальный делитель $%d$%, то красивая расстановка невозможна. Действительно, у нас где-то встречается число $%1$%, и если мы стартуем с него, применяя операцию $%f$%, то получится $%1\prec f(1)\prec f(f(1))\prec\cdots$%, где число всякий раз изменяется на кратное $%d$%, и в такой последовательности никогда не появится число, кратное $%d$%, так как мы стартовали с единицы. Ввиду конечности множества чисел, это будет значить, что мы где-то "перескочили" через $%0$%. Но применение наших правил это исключает: путь от числа $%y$% к числу $%f(y)$% по построению не предполагает этого.

Отображение $%f$% устроено таким образом, что по элементу однозначно восстанавливается его прообраз. Это следует из явного описания. В таких случаях последовательность итераций является чисто периодической, поэтому она приходит к нулю (это верно даже для случая не взаимно простых $%a$% и $%b$%). На каждом шаге итерации мы либо прибавляем $%a$%, либо вычитаем $%b$%, либо делаем то и другое одновременно. Исходя из этого, нетрудно подсчитать общее количество прибавлений $%a$% и вычитаний $%b$%. Если проделать этот подсчёт, исходя из того, что в цикле участвует $%n+1$% число, то окажется, что прибавление $%a$% происходит $%b$% раз, а вычитание $%b$% происходит $%a$% раз. Если допустить, что числа в цикле участвуют не все, то какое-то из этих количеств будет меньше, и тогда не получится "баланса" между $%a$% и $%b$%. Здесь используется взаимная простота: если $%as=bt$% для каких-то натуральных $%s$%, $%t$%, то для взаимно простого случая $%s$% кратно $%b$%, а $%t$% кратно $%a$%. И если какое-то из чисел меньше "нормы" (то есть $%s < b$% или $%t < a$%), то равенство выполняться не может.

Таким образом, доказано, что для взаимно простых $%a$% и $%b$% последовательность итераций $%0$%, $%f(0)$%, $%f(f(0))$%, ... , $%f^{(n)}(0)=b$% исчерпывает все числа от $%0$% до $%n$%. Значит, в красивой расстановке они только так и могут стоять, что влечёт единственность. Последнее, что осталось показать -- это то, что построенная таким образом расстановка в самом деле является красивой. Пока это не было проверено для всех хорд -- только для части из них.

Верен даже более сильный факт: если взять чётное количество различных чисел, расположенных по кругу, то знакочередующаяся сумма отлична от нуля: $%-x_1+x_2-x_3+x_4+\cdots-x_{2k-1}+x_{2k}\ne0$%. Свойство расстановки быть красивой -- это частный случай для $%k=2$%. Доказывается это так: при переходе от числа $%x$% к $%f(x)$% мы либо прибавляем $%a$%, либо вычитаем $%b$%, либо делаем то и другое вместе. Поэтому все разности вида $%x_{2i}-x_{2i-1}$% имеют форму $%p_ia-q_ib$% с неотрицательными коэффициентами $%p_i$%, $%q_i$%. При сложении таких чисел получается число такого же вида, то есть $%pa-qb$%. Выше уже говорилось, что равенство $%pa=qb$% для натуральных $%p,q$% возможно только при $%p\ge b$%, $%q\ge a$% ввиду взаимной простоты чисел $%a$% и $%b$%. Однако такое положение вещей возможно только в одном случае: когда $%p=b$%, $%q=a$%, и при этом учтены все разности между числами. У нас же они учтены не все, так как переход от $%x_2$% к $%x_3$% мы точно не берём.

Это завершает решение задачи, которая кажется мне весьма сложной, и при этом очень интересной.

ссылка

отвечен 17 Апр '14 9:30

изменен 17 Апр '14 15:17

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,932

задан
14 Апр '14 0:23

показан
1090 раз

обновлен
17 Апр '14 15:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru