Олимпиада по математике

[MrDindows]

ewert, для $4k+2, 4k+1$ - точно нельзя. (в прошлом например)
Для остальных всё зависит от начального расположения: Руст написал, что является инвариантом. Раставить можно будет только если инвариант с начала равен нулю, для $4k+2, 4k+1$ это невозможно

[bot]

Вопрос естественно в голову приходил и даже способ уравнивания для нечётного случая наметил, но было не до проверки, да и сейчас пока недосуг, голова уже не варит, а ещё к лекции надо готовиться.

[Руст]

MrDindows в сообщении #368431 писал(а):

ewert, для $4k+2, 4k+1$ - точно нельзя. (в прошлом например)
Для остальных всё зависит от начального расположения: Руст написал, что является инвариантом. Раставить можно будет только если инвариант с начала равен нулю, для $4k+2, 4k+1$ это невозможно

Ошибаетесь, для всех нечетных $n>1$ всегда можно выровнить. Для этого начинаем выровнять к первому, вычитывая или прибавляя вначале второму и третьему, потом третьему и четвертому и т.д. Если в конце один остался не выровненным, то начинаем добавлять остальным по паре (так как нечетное число и осталось не выровненным одно из них) разницу между первым и оставшимся.

[bot]

MrDindows в сообщении #368431 писал(а):

для $4k+2, 4k+1$ это невозможно

Берём $k=1$ в $4k+1$ получаем 5, а на пятёрке способ, о котором говорил сразу после тройки проверил, сейчас ещё раз перепроверил - возможно.

[Руст]

А зачем понадобилось расположение по кругу?
Как я показал, для нечетных оно выравнивается всегда и при расположении в ряд (без операции с парой из последнего и первого). Так же обстоит дело в случае четного количества. Для $n=4k+2$ всегда нельзя, для $n=4k$ зависит от начального положения. Можно выровнить расположенные по кругу, тогда и только тогда, когда можно выровнить расположенные в ряд и наоборот (нельзя выровнить ...).

[MrDindows]

Действительно, с нечётными прогнал)

[ewert]

Ответ:

при нечётных -- всегда можно;
при чётных и не делящихся на 4 -- всегда нельзя;
при делящихся на 4 -- всегда есть конфигурации, когда можно, и всегда есть, когда нельзя.

Решение.

Пусть $x_k$ -- добавка к паре $(a_k,a_{k+1})$, $k=1,2,\ldots,n-1$, и $x_n$ -- к паре $(a_n,a_{1})$. Обнуление означает решение системы:

$\begin{cases}x_1+x_n=-a_1,\\ x_1+x_2=-a_2,\\ x_2+x_3=-a_3,\\.\ .\ .\ .\ .\ .\ .\ .\ .\ .\ .\\ x_{n-1}+x_n=-a_n.\end{cases}$

При нечётных $n$ матица системы невырожденна (детерминант равен двум) и, значит, решение всегда есть. При чётном матрица вырождена и её коранг равен единице. Разрешимость равносильна ортогональности правой части решению однородной сопряженной системы. Это решение единственно (с точностью до постоянного множителя и представляет собой строчку, заполненную чередующимися единицами и минус единицами. Т.е условие разрешимости заключается ровно в том, что сумма чисел, стоящих в чётных позициях, равна сумме для нечётных. Если количество позиций чётно и не делится на 4, то такое никогда невозможно (поскольку нечётна общая сумма). Если делится на четыре -- то всегда найдутся хорошие начальные конфигурации (например, достаточно переставить из упорядоченной расстановки каждую вторую пару); ну и всегда возможны, конечно, и плохие.

-- Вс окт 31, 2010 21:00:28 --

Руст в сообщении #368450 писал(а):

А зачем понадобилось расположение по кругу?

Если цепочка линейна, то это уже другая задача. При этом система оказывается переопределённой и во всех случаях полного ранга. В чётном случае ничего не изменяется. В нечётном решений теперь уже решений может и не быть, т.к. возникает аналогичное условие ортогональности. Т.е. обнулить иногда можно, а иногда нельзя. Но вот выровнять -- действительно, можно всегда, т.к. ортогональности всегда можно добиться прибавлением одного и того же числа ко всем правым частям.

[mihiv]

4.немат. проф.Пусть $P_n(x)$ искомый полином степени n,тогда

$$P'_n(x)(x-a)=qP_n(x).$$

Интегрируем полученное ДУ и получаем $P_n(x)=C(x-a)^q$,т.к.$P_n(x)$-полином,то $q=n$.

[Руст]

ewert в сообщении #368460 писал(а):

Ответ:

Если цепочка линейна, то это уже другая задача. При этом система оказывается переопределённой и во всех случаях полного ранга. В чётном случае ничего не изменяется. В нечётном решений теперь уже решений может и не быть, т.к. возникает аналогичное условие ортогональности. Т.е. обнулить иногда можно, а иногда нельзя. Но вот выровнять -- действительно, можно всегда, т.к. ортогональности всегда можно добиться прибавлением одного и того же числа ко всем правым частям.

Исходная задача для четного, где нет никакой разницы между линейным и круговым случаем.
В нечетном случае для исходного условия выровнить так же нет разницы. Выровнить всегда можно. Разница только в том, что в круговом случае нечетной задачи можно выровнить любому числу, четность которой совпадает с четностью суммы всех чисел, например нулю в случае $n=4k+3$ и единице в случае $n=4k+1$. В круговом случае инвариант работает только по модулю два. В линейной задаче (без использования первой и последней) инвариант работает полностью и можно выровнить только числу инварианту со знаком минус.

[ewert]

Руст в сообщении #368570 писал(а):

в круговом случае нечетной задачи можно выровнить любому числу, четность которой совпадает

Чего-то у Вас тут какая-то путаница. Во-первых, явно перепутаны круговой и некруговой случаи (как раз в круговом и можно выровнять вообще любому, хоть даже и трансцедентному). Во-вторых, в некруговом можно выровнять ровно одному конкретному значению (зависящему от начальной расстановки), а вовсе не любому значению определённой чётности.

[Руст]

ewert в сообщении #368580 писал(а):

Руст в сообщении #368570 писал(а):

в круговом случае нечетной задачи можно выровнить любому числу, четность которой совпадает

Чего-то у Вас тут какая-то путаница. Во-первых, явно перепутаны круговой и некруговой случаи (как раз в круговом и можно выровнять вообще любому, хоть даже и трансцедентному). Во-вторых, в некруговом можно выровнять ровно одному конкретному значению (зависящему от начальной расстановки), а вовсе не любому значению определённой чётности.

Читайте внимательнее. В линейном случае работает инвариант полностью и можно выровнить только $-I$, где $I$ - инвариант. В круговом случае инвариант $I=0\mod 2$ в случае $n=4k+3$ и можно выровнить любому четному числу (но нельзя выровнить нечетному). В случае $n=4k+1$ можно выровнить любому нечетному (нельзя выровнить четному, в частности нулю).

[ewert]

Руст в сообщении #368589 писал(а):

В круговом случае инвариант $I=0\mod 2$ в случае $n=4k+3$ и можно выровнить любому четному числу (но нельзя выровнить нечетному).

В круговом случае можно выровнять вообще любому числу (не забывайте, что добавки по условию задачи -- вещественны). Что означают слова "инвариант работает" -- я просто не понимаю. Если он есть, то он, конечно, может доказать неразрешимость задачи (если она и впрямь неразрешима). Но как он может доказать разрешимость?... Тут инвариантами не отмахнёшься, тут нужен конкретный алгоритм.

Какое-то явное взаимонепонимание. Короче: я предложил абсолютно жёсткое решение, притом в определённом смысле банальное (т.е. не требующее никакой творческой фантазии -- всё автоматически вытекает из постановки задачи и попытки шаблонного её решения, причём очень коротко).

[bot]

Как и ewert, писал системы, но проверять совместность было лениво и недосуг. В поисках более очевидной системы заметил, что в нечётном случае все, кроме одного, можно разбить на пары и стало быть, если возникнет надобность, можно ко всем, кроме одного, добавить одно и то же число.
Когда лёг спать, голова прояснилась и всё стало на свои банальные места - последний трюк надо применить на последнем шаге:

1). Отнимаем первое от первого и второго: 0****...**
2). Отнимаем второе от второго и третьего: 00***...**
............
n-1). Отнимаем n-1-ое от n-1-го и от n-го: 00000...0x

В результате имеем n-1 нолик и $x$ знает что в конце. Если n нечётно, то ко всем ноликам и прибавим этот $x$. Здесь единственное место, где нужна нечётность.
Действий получилось больше, чем в случае системы, но очевиднее.

[ewert]

mihiv в сообщении #368501 писал(а):

Интегрируем полученное ДУ и получаем $P_n(x)=C(x-a)^q$

ДУ -- это, конечно, круто, но как-то чересчур круто. Из $P'_n(x)(x-a)=qP_n(x)$ следует, что кратность любого корня, кроме $a$, для многочленов $P'_n(x)$ и $P_n(x)$ одинакова, а должны эти кратности различаться на единицу. Стало быть, таких корней и вовсе нет.

[Pashka]

ewert в сообщении #368239 писал(а):

bot в сообщении #368209 писал(а):

2. Доказать, что $x^{n^3}-(x+1)^{2n}$ делится на $x^2+x+1.$

Надо доказать, что $e^{{2\pi i\over3}\cdot n^3}=e^{{\pi i\over3}\cdot 2n}$. Т.е. что $e^{{2\pi i\over3}\cdot(n^3-n)}=1$. Т.е. что $n^3-n=n(n-1)(n+1)$ делится на три. Ну это очевидно.

Поясните пожалуйста подробнее!