Графы и комбинаторика.

[Don-Don]

1) В графе 2008 вершин. Докажите, что его рёбра можно покрасить в 1004 цвета так, чтобы не было одноцветных циклов.

Я так понимаю, что граф связный. Иначе можно представить граф из 2008 висячих вершин и задача становится нелепой.
Если граф связный, то для цикла нужно хотя бы три вершины и три ребра одноцветных. Можно красить в один цвет два ребра. Просто неизвестны ведь степени вершин, не за что зацепиться.

2) Найти сумму комбинаторно, не используя формул $C_n^0-C_n^1+C_n^2-....+(-1)^nC_n^n$.

Смысл $C_n^k$ -- число способов из $n$ выбрать $k$. Тут же количество объектов фиксированно, а выбранные объекты меняются. Но какой прок их суммировать с разными знаками, пока не очевидно, с чего же здесь начать?

3) Может ли $m!+n!$ оканчиваться на $1990$?

Пусть $n>m$ для определенности. $m!+n!=m!(1+(n-m)!)$

$1990=199\cdot 5\cdot 2$.

Мне кажется, что все-таки нет. Нужно смотреть сравнимость по малым модулям, как мне кажется, но что-то это не помогло.

[Lia]

Тема перемещена из форума «Загадки, головоломки, ребусы» в форум «Помогите решить / разобраться (М)»

[2old]

Don-Don
2. Можно в $(1+x)^n$ подставить $-1$ и увидеть ответ. Комбинаторно можно как-то так: число подмножеств с четным числом элементов равно числу подмножеств с нечетным числом элементов. Предположим это не так, тогда всего подмножеств было бы нечетное число, что очевидно неправда.

[nnosipov]

Don-Don в сообщении #1007859 писал(а):

Пусть $n>m$ для определенности. $m!+n!=m!(1+(n-m)!)$

Это правильно. А теперь подумайте, может ли $m$ быть слишком большим, если число оканчивается на $90$.

[iifat]

2old в сообщении #1007875 писал(а):

Предположим это не так, тогда всего подмножеств было бы нечетное число

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

-- 26.04.2015, 02:06 --

Don-Don в сообщении #1007859 писал(а):

Я так понимаю, что граф связный. Иначе можно представить граф из 2008 висячих вершин и задача становится нелепой

Хм. Тоже как-то ничего не понимаю. Почему граф непременно связный? Что нелепого в случае графа из 2008 отдельных вершин?

[2old]

iifat
Да, я ошибся, спасибо.
Если $n$ нечетное, то такой биекцией будет просто дополнение.
Если четное, то выкидываем элемент $n$. Получили выше описанный случай, равное количество подмножеств с четным и нечетным числом элементов. Теперь получим все подмножества, содержащие $n$, добавляя его во сначала во все подмножества с четным числом элементов -- они станут с нечетным числом элементов, и наоборот. Значит мы увеличили количество помножеств каждого вида одинаково.

[iifat]

При любом $n$. Фиксируем любой элемент множества и сопоставляем два множества, отличающиеся только наличием этого элемента. Одно подмножество будет с чётным числом элементов, другое с нечётным.

[2old]

iifat
Да, вы эту простую мысль лучше изложили

-- 25.04.2015, 21:18 --

nnosipov
$m\leq 9$ иначе произведение будет кратно $100$ и там $90$ уже не получить. А дальше что делать?

[ИСН]

Don-Don в сообщении #1007859 писал(а):

Пусть $n>m$ для определенности. $m!+n!=m!(1+(n-m)!)$

Радикальный подход. То есть Вы утверждаете, что $n!=m!(n-m)!$? Действительно ли это верно? Всегда ли это верно? Проверьте на каких-нибудь числах.
Ну и насчёт сравнимости по малым модулям - могу лишь предположить, что Вы пробовали сравнимость по недостаточно малым модулям, потому что как иначе было не найти противоречия, я не знаю.

[grizzly]

Don-Don в сообщении #1007859 писал(а):

$1990=199\cdot 5\cdot 2$.

Это выражение не похоже на факториал. А может ли у факториала последняя цифра быть 0, а предпоследняя -- нечётная? Почему? А какая цифра будет предпоследней, если сложить две чётные?

-- 25.04.2015, 22:18 --

Ну можно, конечно, получить в сумме нечётную перед нулём, но только так $30=6+24$.

-- 25.04.2015, 22:40 --

Ага, ИСН двумя строчками выше об этом уже сказал.

[sqribner48]

Don-Don
По первой задаче
Может быть имеет смысл рассмотреть самый худший случай -- когда граф является полным графом $K_{2008}$. Этот граф можно представить, как цикл из 2008 вершин, а внутри него расположены все остальные ребра.
Используя такой подход, нетрудно заметить, что ребра полного графа $K_4$ можно закрасить двумя $(4/2=2)$ цветами, а ребра полного графа $K_6$ можно раскрасить тремя $(6/2=3)$ цветами без образования одноцветных циклов.
Может это даст Вам какую-то исходную зацепку в поиске решения.