Олимпиадные задачи по теме «Комбинаторика» - сложность 2-3 с решениями
При каком <i>n</i> > 1 может случиться так, что в компании из <i>n</i> + 1 девочек и <i>n</i> мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики – с одним и тем же числом девочек?
а) Может ли случиться, что в компании из 10 девочек и 9 мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики – с одним и тем же числом девочек?
б) А если девочек 11, а мальчиков 10?
На плоскости дан квадрат 8×8, разбитый на клеточки 1×1. Его покрывают прямоугольными равнобедренными треугольниками (два треугольника закрывают одну клетку). Имеется 64 черных и 64 белых треугольника. Рассматриваются "правильные" покрытия – такие, что каждые два треугольника, имеющие общую сторону, разного цвета. Сколько существует правильных покрытий?
В каждой клетке квадрата 8×8 клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть
а) больше 15?
б) больше 20?
Пусть <i>n</i> и <i>b</i> – натуральные числа. Через <i>V</i>(<i>n, b</i>) обозначим число разложений <i>n</i> на сомножители, каждый из которых больше <i>b</i> (например:
36 = 6·6 = 4·9 = 3·3·4 = 3·12, так что <i>V</i>(36, 2) = 5). Докажите, что <i>V</i>(<i>n, b</i>) < <sup><i>n</i></sup>/<sub><i>b</i></sub>.
В пространстве заданы четыре точки, не лежащие в одной плоскости.
Сколько существует различных параллелепипедов, для которых эти точки служат вершинами?
а) Докажите, что нельзя занумеровать рёбра куба числами 1, 2, ..., 11, 12 так, чтобы для каждой вершины сумма номеров трёх выходящих из неё рёбер была одной и той же. б) Можно ли вычеркнуть одно из чисел 1, 2, ..., 12, 13 и оставшимися занумеровать рёбра куба так, чтобы выполнялось то же условие?
В каждой клетке квадрата 8×8 клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть больше
а) 15;
б) 20?
в) Может ли в аналогичной задаче про квадрат <i>n×n</i> клеток получиться больше чем <sup><i>n</i>²</sup>/<sub>4</sub> частей (для <i>n</i> > 8)?