Выбрана 1 задача 
Убрать все задачи
Дан клетчатый квадрат $n\times n$, где $n$ > 1. Кроссвордом будем называть любое непустое множество его клеток, а словом – любую горизонтальную и любую вертикальную полоску (клетчатый прямоугольник шириной в одну клетку), целиком состоящую из клеток кроссворда и не содержащуюся ни в какой большей полоске из клеток кроссворда (ни горизонтальной, ни вертикальной). Пусть $x$ – количество слов в кроссворде, $y$ – наименьшее количество слов, которыми можно покрыть кроссворд. Найдите максимум отношения $\frac{x}{y}$ при данном $n$.
Решение
|
|
 |
Условие
Пусть n и b – натуральные числа. Через V(n, b) обозначим число разложений n на сомножители, каждый из которых больше b (например:
36 = 6·6 = 4·9 = 3·3·4 = 3·12, так что V(36, 2) = 5). Докажите, что V(n, b) < n/b.
Решение
Индукция по n. База (n = 1) очевидна: V(1, b) = 0.
Шаг индукции. Предположим теперь, что это неравенство верно при всех m < n.
Для каждого делителя k > b числа n рассмотрим все разложения числа n, в которых минимальный сомножитель равен k. Количество таких разложений равно V(n/k, k – 1). Исключение составляет случай k = n – такое разложение одно, а V(n/n, n – 1) = 0. Следовательно,
Замечания
12 баллов
