Imo 2009 6 мое решение

[DARIUS]

Даны попарно различные целые положительные числа $a_1 a_2 ... a_n$ а также множество $M$,состоящие из $n-1$ целого положительного числа,но не содержащие число $s=a_1+a_2+...a_n$.Кузнечик должен сделать $n$ прыжков вправо по числовой прямой стартуя из точки с координатой 0.При этом длины его прыжков должны равняться числам $a_1 a_2 ...a_n $ взятых в некотором порядке.Докажите что этот порядок можно выбрать таким образом что-бы кузнечик ни разу не приземлился в точке имеющей координату из множества $M$.В официальном решении используется довольно специфическая индукция.Мое решение. Ясно что нас интересуют только те элементы множества $М$ которые являются некоторой суммой исходных чисел.Число всех возможных прыжков кузнечика из исходной точки в конечную это число цепей всего их $n!$,число цепей содержащих данный элемент множества $k$ это $(n-1)!(n-k)!$,просуммировав по всем $k$,и сократив каждое слагаемое на $k!$(так как множество путей содержащих данный элемент входит в сумму $k!$),минимальный элемент данной суммы $ \frac 1 {(n-1)!}$,таким образом количество всех цепей больше количества проходящих через данный элемент минимум в $n$ раз ,поэтому у кузнечика есть по меньшей мере $n$ путей удовлетворяющих условию.Нет ли здесь ошибок?

-- 05.12.2022, 20:06 --

Все таки заключение-неверно,у кузнечика должно быть не $n$ возможных путей ,а только один.

[mihaild]

DARIUS в сообщении #1572677 писал(а):

число цепей содержащих данный элемент множества $k$ это $(n-1)!(n-k)!$,

Вот это непонятно. Что такое $k$ - частичная сумма (явно нет, она может быть больше чем $n$)?

[DARIUS]

Это $k$ элементное множество,для простоты можно считать все числа степенями двойки.Мне кажется ,что данная задача в какой-то интерпретации должна быть у Кнута,ну не мог Мастер пройти мимо,можете подсказать ссылку кто хорошо держит структуру книг в голове?

-- 05.12.2022, 21:15 --

Да действительно .Число цепей проходящих через элемент множества $k$ это $k!(n-k)!$ правда на остальные шаги решения это никак не влияет.Но все-равно решение получилось совсем элементарное по сравнению с официальным .

[mihaild]

Всё еще непонятно. Взяли какое-то $k$, взяли $k$-элементное множество, взяли его элемент, посчитали число путей, проходящих через него? Так это не зависит от $k$ и зависит от элемента.

DARIUS в сообщении #1572689 писал(а):

Число цепей проходящих через элемент множества $k$ это $k!(n-k)!$

Это выглядит похоже на "пусть мы разбили прыжки на две группы, из $k$ и из $n - k$, и считаем число путей, в которых используются сначала элементы первой группы, а потом второй".
Но если это используется как "число путей, проходящих через число - сумму элементов первой группы", то это неверно, потому что могут быть и другие способы получить ту же сумму.

[DARIUS]

mihaild в сообщении #1572710 писал(а):

Всё еще непонятно. Взяли какое-то $k$, взяли $k$-элементное множество, взяли его элемент, посчитали число путей, проходящих через него? Так это не зависит от $k$ и зависит от элемента.

Нет ,так $k$
(как подмножество) и есть элемент цепи,я и предложил рассматривать все числа как степени двойки чтобы избавиться от всего связанного с множествами Сидона.

[mihaild]

Всё равно не понял. Взяли какое-то множество $X$ из $k$ элементов. Вы считаете множество путей, проходящих через все элементы $X$? Ну так оно очень сильно зависит от $X$.

DARIUS в сообщении #1572712 писал(а):

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

Какие числа? $a_i$? Ну так происходящее очень сильно зависит от них, если они таковы, что суммы двух различных подмножеств отличаются (как со степенями двойки), то задача становится тривиальной.

[DARIUS]

mihaild в сообщении #1572714 писал(а):

Это выглядит похоже на "пусть мы разбили прыжки на две группы, из $k$ и из $n - k$, и считаем число путей, в которых используются сначала элементы первой группы, а потом второй".
Но если это используется как "число путей, проходящих через число - сумму элементов первой группы", то это неверно, потому что могут быть и другие способы получить ту же сумму.

В моем решении структура избегаемого множества вообще не учитывается,если какая-то сумма будет получена разными вариантами ,то они будут учитываться в разных цепях,,множество $k$,это просто определенное число слагаемых исходных чисел

-- 06.12.2022, 00:01 --

Решение мне кажется можно перевести на язык теории графов,с использованием ,,Гамильтонова цикла " и средней степени вершин.

[mihaild]

Всё равно не понимаю. Вот у нас есть числа $a_i$. Вы посчитали число способов их упорядочить, удовлетворяющих какому-то свойству, способов получилось $n! (n - k)!$, так?
Что это за свойство?

[DARIUS]

Решение такое ,для начала вообще забудем про структуру избегаемого множества,нас даже не волнуют сами числа $a_n$,кроме того,что они различны.Множество всех цепей от $\varnothing $ до $A_n$$ = $$a_1 +a_2+... a_n$ состоит из $n!$ элементов.Теперь будем рассматривать возможные суммы,ясно что нас интересуют только те элементы избегаемого множества которые представляют сумму некоторых элементов исходного,поэтому нам просто достаточно рассмотреть все цепи проходящие через данный элемент (то есть состоящие из данного числа слагаемых $k$) их число $k!(n-k)!$(в исходном решении была ошибка) но при этом это число надо сократить на $k!$ как число цепей содержащее $k$ элементов, получаем сумму $(n-1)!+(n-2)! +...1$ она очевидно меньше числа всех цепей ,значит существует путь проходящий по всем элементам цепи но не содержащий ни одного элемента множества $M$(структуру множества $M $ мы вообще не рассматривали)

[mihaild]

DARIUS в сообщении #1572738 писал(а):

Множество всех цепей от $\varnothing $ до $A_n[math]$$ = $$a_1 +a_2+... a_n$[/math] состоит из $n!$ элементов

Так, я не понимаю, что такое цепь в данном контексте. Из этого предложения кажется, что это просто упорядочение элементов $a_i$, но ниже вы говорите про цепи, состоящие из $k$ элементов.
А $\varnothing$ это $0$, или вы еще как-то множества сюда запихиваете?

[TOTAL]

DARIUS в сообщении #1572738 писал(а):

Решение такое ,для начала вообще забудем про структуру избегаемого множества,нас даже не волнуют сами числа $a_n$,кроме того,что они различны.Множество всех цепей от $\varnothing $ до $A_n$$ = $$a_1 +a_2+... a_n$ состоит из $n!$ элементов.Теперь будем рассматривать возможные суммы,ясно что нас интересуют только те элементы избегаемого множества которые представляют сумму некоторых элементов исходного,поэтому нам просто достаточно рассмотреть все цепи проходящие через данный элемент

Элемент равен $K$. Сколько цепей проходит через этот элемент?

[DARIUS]

TOTAL в сообщении #1572764 писал(а):

Элемент равен $K$. Сколько цепей проходит через этот элемент?

$K!(n-K)!$

-- 06.12.2022, 12:14 --

mihaild в сообщении #1572743 писал(а):

А $\varnothing$ это $0$, или вы еще как-то множества сюда запихиваете?

Мне кажется при использовании цепей корректней начинать с пустого множества а не с нуля.

-- 06.12.2022, 12:22 --

Цепь в данном контексте ,это строго расширяющаяся последовательность множеств начинающаяся с $\varnothing$ и заканчивающаяся $\{a_1,a_2...,a_n\}$

[mihaild]

DARIUS в сообщении #1572790 писал(а):

Цепь в данном контексте ,это строго расширяющаяся последовательность множеств начинающаяся с $\varnothing$ и заканчивающаяся $\{a_1,a_2...,a_n\}$

А что значит "цепь содержит элемент" - элементом является подмножество $\{a_1, \ldots, a_n\}$, и он принадлежит этой расширяющейся последовательности? Тогда от него нельзя брать факториал.

DARIUS в сообщении #1572790 писал(а):

TOTAL в сообщении #1572764 писал(а):

Элемент равен $K$. Сколько цепей проходит через этот элемент?

$K!(n-K)!$

А если вместо этого брать факториал мощности, то получится неправда: $A = \{1, 2\}$, $K = \{1\}$, есть две цепи: $\varnothing, \{1\}$ и $\varnothing, \{1\}, \{1, 2\}$.

[DARIUS]

Цепь содержит элемент-значит цепь содержит $k$ элементное подмножество,в принципе можно оставить одни индексы,цепь всегда заканчивается множеством содержащим все элементы в примере что-то не так.

[mihaild]

DARIUS в сообщении #1572801 писал(а):

значит цепь содержит $k$ элементное подмножество

Так $k$ это число или подмножество?
Давайте попробую угадать: вы хотите сказать, что цепь - это не просто возрастающая последовательность множеств, начинающаяся с пустого и заканчивающегося $A$, но еще и содержащая $n + 1$ элемент. И для произвольного $k$-элементного подмножества множества $A$, количество его содержащих цепей равно $k! (n - k)!$. Вы это имели в виду? Если да, то почему до этого приходится догадываться читателям? Если нет, то сформулируйте четко что у вас там за утверждение про $K$ и $k$.
Если да, то вы потом зачем-то их суммируете, непонятно зачем. Так можно было бы показать, что для фиксированной цепи существует с ней не пересекающаяся (кроме как в начале и в конце), но нас же не это спрашивали.