Олимпиадные задачи по теме «Комбинаторика» - сложность 2-3 с решениями
В стране несколько городов, соединённых дорогами с односторонним и двусторонним движением. Известно, что из каждого города в любой другой можно проехать ровно одним путём, не проходящим два раза через один и тот же город. Докажите, что страну можно разделить на три губернии так, чтобы ни одна дорога не соединяла два города из одной губернии.
Али-Баба стоит с большим мешком монет в углу пустой прямоугольной пещеры размером <i>m×n</i> клеток, раскрашенных в шахматном порядке. Из любой клетки он может сделать шаг в любую из четырёх соседних клеток (вверх, вниз, вправо или влево). При этом он должен либо положить одну монету в этой клетке, либо забрать из неё одну монету, если, конечно, она не пуста. Может ли после прогулки Али-Бабы по пещере оказаться, что на чёрных клетках лежит ровно по одной монете, а на белых монет нет?
Существуют ли такие иррациональные числа <i>a</i> и <i>b</i>, что <i>a </i> > 1, <i>b</i> > 1, и [<i>a<sup>m</sup></i>] отлично от [<i>b<sup>n</sup></i>] при любых натуральных числах <i>m</i> и <i>n</i>?