Раскраска графа

[Юстас]

Пусть $G$ - двудольный граф(то есть множество вершин можно разбить на 2 подмножества так что каждое ребро соединяет вершины из разных множеств) с $n$ вершинами. Каждой вершине поставлена в соответствие палитра из не менее чем $\log n$ цветов(возможно разных для разных вершин). Доказать, что существует раскраска графа, такая что каждое ребро соединяет вершины разных цветов и каждая вершина покрашена цветом из своей палитры.

[maxal]

Наверное, всё-таки число цветов должно быть строго больше чем $\log_2 n$ - в противном случае существует контрпример уже с $n=2$. И здесь, кстати, важно, что логарифм двоичный - пришлось додумывать это за вас.

Задача решается стандартной техникой, восходящей к Эрдёшу.

Пусть $k=1+\lfloor \log_2 n\rfloor$, т.е. наименьшее целое число строго большее чем $\log_2 n$. Выкинув "лишние" цвета, будем считать, что палитра каждой вершины состоит ровно из $k$ цветов.

Пусть $C$ - множество всех цветов из всех палитр. Случайным равномерным образом назовем каждый цвет из $C$ "левым" или "правым". Тогда вероятность, что у вершины в палитре есть хотя бы один левый и хотя бы один правый цвет, равна $1-\frac{2}{2^k}> 1-\frac{2}{n},$ а ожидаемое число таких вершин $E(N)$, в силу линейности мат.ожидания, строго больше $n\cdot \left(1-\frac{2}{n}\right)=n-2.$

Поэтому существует такая разбивка цветов на левый-правый, что $N\geq n-1$. Рассмотрим два случая:

1) $N=n$. В этом случае произвольно называем доли графа "левой" и "правой", вершины из левой доли красим левыми цветами из их палитр, вершины из правой доли - правыми цветами из их палитр. Требование задачи, очевидно, выполнено.

2) $N=n-1$. В этом случае существует одна вершина, вся палитра которой левая (для определенности). В этом случае называем долю, которой принадлежит эта вершина, "левой", а другую долю - "правой", и далее красим как в случае 1).

[Юстас]

Да, все верно, в Вас я не сомневался . И спасибо за поправки - писал по памяти. Вот еще задача из этой оперы - посложнее:
имеется набор $X$ из $4k^2$ вычетов по простому модулю $p$. Доказать, что существует $a$ такое что множество вида $\left\{ax\mod p, \ x\in X\right\}$ имеет непустое пересечение с каждым интервалом $\mathbb Z_p$ из не менее чем $\frac{p}{k}$ чисел.