Школьные задачи по математике

Irbis-S

Подскажите плз идею решения, никак не соображу что-то :
1) Дан связный граф, степень любой вершины чётна. Доказать:
a) Есть простой цикл
б) Рёбра можно разбить на несколько циклов с общими вершинами, но без общих рёбер
в) Есть цикл, содержащий все рёбра.
2) В турнире каждая команда сыграла с каждой по разу, ничьих не было. Вопрос: всегда ли можно расположить команды в том порядке,чтоб 1я выиграла у 2й, 2я у 3й и тд...
3) Есть 450 человек. Каждый дал яблоко другому ( одному). Доказать, что можно выбрать 150 человек, среди которых никто никому не дал яблоко

griz_a

а) Возьмем вершину какую-нибудь. Пойдем из нее по ребрам. Каждый раз, пока не вернемся ни в одну из вершин, где уже были, у нас будет выбор, куда пойти. Таким образом найдем цикл.
б) Возьмем цикл. Выкинем его. Останется набор связных графов с тем же свойством. Повторим. И так далее.
в) Выйдем из какой-то вершины и будем ходить. Нам ничего не остается, как вернуться в исходную, иначе она нечетная. Из тех же рассуждений вернемся опять. И т.д.

incwizitor

2) В турнире каждая команда сыграла с каждой по разу, ничьих не было. Вопрос: всегда ли можно расположить команды в том порядке,чтоб 1я выиграла у 2й, 2я у 3й и тд...
а если есть две команды, которые всем слили, то как их вставить в эту цепочку?
3) Есть 450 человек. Каждый дал яблоко другому ( одному). Доказать, что можно выбрать 150 человек, среди которых никто никому не дал яблоко
прошу уточнить условие. если чувак с номером N даст яблоко чуваку с номером (N+1)%450, то не получится выбрать 150 искомых человек.

griz_a

а если есть две команды, которые всем слили, то как их вставить в эту цепочку?

первая из них проиграла второй, а вторая первой и все за один матч? :ooo:
"если чувак с номером N даст яблоко чуваку с номером (N+1)%450, то не получится выбрать 150 искомых человек."
Почему? :confused:

incwizitor

первая из них проиграла второй, а вторая первой и все за один матч?
да, это я отмочил
"если чувак с номером N даст яблоко чуваку с номером (N+1)%450, то не получится выбрать 150 искомых человек."
Почему?
ну так каждый чувак дал кому-то яблоко.
не понял задачу =\

griz_a

Так по условию каждый дал. Вопрос в том, что внутри 150 никто никому яблок не передавал

incwizitor

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

Xephon

Решение 3-ей задачи:
Составим граф, где стрелка идёт от давшего яблоко к тому, кто яблоко получил.
Такой граф распадается на некоторое количество компонент связности, каждая из которых есть цикл.
В каждом цикле можно участников занумеровать от 1 и до последнего, и выбрать из них только тех, у которых номера чётные. Таких человек будет не меньше чем длина цикла поделить на 3 (ровно столько будет для цикла из 3 человек).
В сумме мы наберём не меньше 150 человек, лишних можно выкинуть :)

shpanenoc

в) Выйдем из какой-то вершины и будем ходить. Нам ничего не остается, как вернуться в исходную, иначе она нечетная. Из тех же рассуждений вернемся опять. И т.д.
Это же Эйлеров цикл :)
Я бы модифицировал построение так:
1. Выйдем из какой-то вершины и будем ходить. Нам ничего не остается, как вернуться в исходную, иначе она нечетная.
2. Получился цикл. Если этот цикл не искомый, то есть от него где-то непройденное ответвление (из связности графа). Двинувшись по нему (при этом ходя только по непройденным ребрам по соображениям пункта 1 вернемся в ту же точку. Полученный виток вставляем в наш цикл в соответствующее место.

incwizitor

2) В турнире каждая команда сыграла с каждой по разу, ничьих не было. Вопрос: всегда ли можно расположить команды в том порядке,чтоб 1я выиграла у 2й, 2я у 3й и тд...
попробуем по индукции
для 2 очевидно
допустим, доказано для N, что существует порядок: z1 > z2 >...> zN
пусть есть группа из N + 1. разделим группу произвольно на 1 (t) + N
допустим, что t нельзя вставить в цепочку z1 > z2 > ... > zN, тогда получаем, что t < z1
Если t > z2, то у нас получилось вставить t между z1 и z2 => t < z2
аналогично, получаем t < z3
и тд
получаем t < zN => z1 > z2 > .. > zN > t => то есть удалось вставить t

Skilet3d

Такой граф распадается на некоторое количество компонент связности, каждая из которых есть цикл.
В каждом цикле можно участников занумеровать от 1 и до последнего, и выбрать из них только тех, у которых номера чётные. Таких человек будет не меньше чем длина цикла поделить на 3 (ровно столько будет для цикла из 3 человек).
Это будут не циклы а компоненты графа с циклами а по поводу трети надо ещё доказать

griz_a

А если пятеро дали одному яблоко, то где цикл? :confused:
Докажем по индукции, что треть можно.
Для 1, 2, 3 - готово.
Пусть для n доказано, докажем для n+3
Есть человек, который связан яблоковзятством и яблокодатством не более чем с двумя.
Тогда выкинем его, того кому он давал яблоко и того, кто дал ему. Среди оставшихся можно выбрать треть, никто из которых никому не давал яблок. Этот человек с ними тоже не связан.

Skilet3d

А если пятеро дали одному яблоко, то где цикл?
этот человек тоже кому то дал яблоку, а тот кому он дал тоже дал яблоку кому-то и т.д. рано или поздно цикл будет, но к твоему решению это отношения не имеет)

Skilet3d

попробуем по индукции
для 2 очевидно
допустим, доказано для N, что существует порядок: z1 > z2 >...> zN
пусть есть группа из N + 1. разделим группу произвольно на 1 (t) + N
допустим, что t нельзя вставить в цепочку z1 > z2 > ... > zN, тогда получаем, что t < z1
Если t > z2, то у нас получилось вставить t между z1 и z2 => t < z2
аналогично, получаем t < z3
и тд
получаем t < zN => z1 > z2 > .. > zN > t => то есть удалось вставить t
понятнее будет если объяснить так
допустим, доказано для N, что существует порядок: z1 > z2 >...> zN
пусть есть группа из N + 1. разделим группу произвольно на 1 (t) + N
упорядочим отделенные N команд как это сказано в условии,
если оставшаяся команда выиграла у первой то она становится первой и все доказано,
предположим что отделенная команда проиграла первой, тогда идем по списку до первой команды у которой она выиграла пусть это будет команда k, тогда t проиграла k-1 и выиграла у k между ними и вставляем, в случае если команда t проиграла всем командам, вставляем её последней

Xephon

А если пятеро дали одному яблоко, то где цикл?
Ты прав, решение не проходит.
Я почему-то предполагал, что никто больше одного яблока не получит...

incwizitor

3) Есть 450 человек. Каждый дал яблоко другому ( одному). Доказать, что можно выбрать 150 человек, среди которых никто никому не дал яблоко
накумекал с приятелем такое решение:
пусть M - исходное множество
докажем, что искомая группа имеет размер >= |M| / 3
"люди Икс" - группа людей, которые друг другу не давали яблоко
выберем "максимальную" группу A, такую что в ней все "люди Икс". эта группа непустая (1 человека можно всегда в нее поместить а под максимальностью понимается невозможность добавить в нее кого-то еще.
имеем разбиение M = A U D
все люди из A дали свое яблоко кому-то из D. обозначим всех этих людей через группу B, а остальных - C
имеем: M = A U B U C
отмечу, что |B| <= |A|
Рассмотрим группу C:

  • если она пустая, то |A| >= |M| / 2 >= |M| / 3, чтд.
  • если она пустая, то это группа людей Икс! Действительно, если кто-то из C дал соседу яблоко из C, то это чувака можно поместить в группу A, а это будет противоречить максимальности группы A

Таким образом мы имеем две группы людей Икс: A, C и дополнение размером <= |A|
Если обе группы < |M| / 3, то |A| + |B| + |C| <= 2*|A| + |C| < |M|. Противоречие разбиению множества M.
Значит, нашлась группа людей Икс (A или C) размера >= |M| / 3.

incwizitor

попробовал изобразить решение на картинке =)

incwizitor

Докажем по индукции, что треть можно.
Для 1, 2, 3 - готово.
Пусть для n доказано, докажем для n+3
Есть человек, который связан яблоковзятством и яблокодатством не более чем с двумя.
Тогда выкинем его, того кому он давал яблоко и того, кто дал ему. Среди оставшихся можно выбрать треть, никто из которых никому не давал яблок. Этот человек с ними тоже не связан.
мне кажется, что шаг индукции надо аккуратнее делать
"оставшиеся" не удовлетворяют условию задачи, т.к. им извне могли яблоко дать и они вовне отдать могли
зы. в вашем решение так мало подробностей, что оно представляет из себя очередную задачу :grin:
зы2: из вашего док-ва следует более строгое утверждение: искомую группу можно набрать из людей, которым дали не более одного яблока. пытаюсь понять верно ли это ...

griz_a

Вот уж не знаю, каких подробностей в нём мало.
Я пропустил две вещи как тривиальные. Первая - что из 1, 2, 3 можно выбрать 1 человека, удовлетворяющего условию :)
Вторая - что если при переходе "оставшиеся" отдают яблоки на сторону, то можно добавить передач недостающих яблок внутри искусственно. Если мы при таких условиях сможем выбрать треть, то в исходном и подавно.

iri3955

А можно так:
Берём любую команду, выигравших ставим перед ней, проигравших за ней.
Обе группы (выигравшие и проигравшие) внутри сортируем
PROFIT

incwizitor

у меня была сортировка вставками, а у тебя quicksort :grin:
Оставить комментарий
Имя или ник:
Комментарий: