Олимпиадные задачи по теме «Комбинаторика» для 9-10 класса - сложность 4 с решениями
Клетчатый квадрат 2010×2010 разрезан на трёхклеточные уголки. Докажите, что можно в каждом уголке отметить по клетке так, чтобы в каждой вертикали и в каждой горизонтали было поровну отмеченных клеток.
В стране есть <i>N</i> городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого <i>k</i> (2 ≤ <i>k ≤ N</i>) при любом выборе <i>k</i> городов количество авиалиний между этими городами не будет превосходить 2<i>k</i> – 2. Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.
Имеются три комиссии бюрократов. Известно, что для каждой пары бюрократов из разных комиссий среди членов оставшейся комиссии есть ровно 10 бюрократов, которые знакомы с обоими, и ровно 10 бюрократов, которые незнакомы с обоими. Найдите общее число бюрократов в комиссиях.
Сколькими способами числа 2<sup>0</sup>, 2<sup>1</sup>, 2², ..., 2<sup>2005</sup> можно разбить на два непустых множества <i>A</i> и <i>B</i> так, чтобы уравнение <i>x</i>² – <i>S</i>(<i>A</i>)<i>x + S</i>(<i>B</i>) = 0, где <i>S</i>(<i>M</i>) – сумма чисел множества <i>M</i>, имело целый корень?
У фокусника и помощника есть колода с картами; одна сторона ("рубашка") у всех карт одинакова, а другая окрашена в один из 2017 цветов (в колоде по 1000000 карт каждого цвета). Фокусник и помощник собираются показать следующий фокус. Фокусник выходит из зала, а зрители выкладывают на стол в ряд <i>n</i> > 1 карт рубашками вниз. Помощник смотрит на эти карты, а затем все, кроме одной, переворачивает рубашкой вверх, не меняя их порядка. Затем входит фокусник, смотрит на стол, указывает на одну из закрытых карт и называет её цвет. При каком наименьшем <i>k</i> фокусник может заранее договориться с помощником так, чтобы фокус гарантированно удался?
На каждой из 2013 карточек написано по числу, все эти 2013 чисел различны. Карточки перевёрнуты числами вниз. За один ход разрешается указать на десять карточек, и в ответ сообщат одно из чисел, написанных на них (неизвестно, какое).
Для какого наибольшего <i>t</i> гарантированно удастся найти <i>t</i> карточек, про которые известно, какое число написано на каждой из них?