Разделы 
Дополнительно
Задача по математике - 3588
2019-06-12 
Можно ли разместить 1965 точек в квадрате со стороной 1 так, чтобы любой прямоугольник площади 1/200 со сторонами, параллельными сторонам квадрата, содержал внутри хотя бы одну из этих точек?
Решение:
В квадрате $0 \leq x \leq 1, 0 \leq y \leq 1$, на прямой $у = 1/2$ равномерно расставим $с_0 = 200$ точек: $(k/201; 1/2), k = 1, 2, \cdots, 200$. Затем на каждой из прямых $у = 1/4$ и $у = 3/4$ расставим по $c_1 = 100$ точек $(k/101; 1/4), (k/101; 3/4), к = 1, 2, \cdots, 100$. Повторяя этот процесс, для $m = 2, 3, \cdots, 7$ на каждой прямой $у = (2l - 1)^{2-m-1}$, $1 \leq l \leq 2^m$, расставим по $c_m$ точек $\left ( \frac {k}{c_m + 1}; \frac {2l - 1}{2^{m+1}} \right )$, где $с_m = [200 \cdot 2^{-m}]$ (при $m = 7$ на 128 соответствующих прямых будет поставлено по одной точке). Всего поставлено
$\sum_{m=0}^7 2^m c_m = 200 + 2 \cdot 100 + 4 \cdot 50 + 8 \cdot 25 + 16 \cdot 12 + 32 \cdot 6 + 64 \cdot 3 + 128 = 1704$ точек.
Эту конструкцию поясняет рис.
Ясно, что никакой прямоугольник площади 1/200 не втиснется между расставленными точками. Если он пересекает прямую $у = 1/2$, то его основание не больше 1/201; если нет, то он расположен целиком выше или ниже этой прямой. При этом, если он пересекает прямую $у = 3/4$ или $у = 1/4$, его высота не больше 1/2, а основание не больше 1/101 и т. д. Если прямоугольник целиком расположен между прямыми вида $у = n/256 (n = 1, 2, \cdots, 255)$, то его высота не больше $1/256$.
Ответ: можно.
Можно ли разместить 1965 точек в квадрате со стороной 1 так, чтобы любой прямоугольник площади 1/200 со сторонами, параллельными сторонам квадрата, содержал внутри хотя бы одну из этих точек?
Решение:
В квадрате $0 \leq x \leq 1, 0 \leq y \leq 1$, на прямой $у = 1/2$ равномерно расставим $с_0 = 200$ точек: $(k/201; 1/2), k = 1, 2, \cdots, 200$. Затем на каждой из прямых $у = 1/4$ и $у = 3/4$ расставим по $c_1 = 100$ точек $(k/101; 1/4), (k/101; 3/4), к = 1, 2, \cdots, 100$. Повторяя этот процесс, для $m = 2, 3, \cdots, 7$ на каждой прямой $у = (2l - 1)^{2-m-1}$, $1 \leq l \leq 2^m$, расставим по $c_m$ точек $\left ( \frac {k}{c_m + 1}; \frac {2l - 1}{2^{m+1}} \right )$, где $с_m = [200 \cdot 2^{-m}]$ (при $m = 7$ на 128 соответствующих прямых будет поставлено по одной точке). Всего поставлено
$\sum_{m=0}^7 2^m c_m = 200 + 2 \cdot 100 + 4 \cdot 50 + 8 \cdot 25 + 16 \cdot 12 + 32 \cdot 6 + 64 \cdot 3 + 128 = 1704$ точек.
Эту конструкцию поясняет рис.
Ясно, что никакой прямоугольник площади 1/200 не втиснется между расставленными точками. Если он пересекает прямую $у = 1/2$, то его основание не больше 1/201; если нет, то он расположен целиком выше или ниже этой прямой. При этом, если он пересекает прямую $у = 3/4$ или $у = 1/4$, его высота не больше 1/2, а основание не больше 1/101 и т. д. Если прямоугольник целиком расположен между прямыми вида $у = n/256 (n = 1, 2, \cdots, 255)$, то его высота не больше $1/256$.
Ответ: можно.
