Аннотация:
В проективной плоскости $PG(2,q)$ рассматривается итеративная конструкция полных дуг, добавляющая одну новую точку на каждом шаге. Доказано, что непокрытые точки равномерно распределены на плоскости. Для более чем половины шагов итеративного процесса доказана оценка числа новых покрытых точек. Сделано естественное (и обоснованное) предположение, что эта оценка справедлива и для остальных шагов. В результате получены верхние границы наименьшего размера $t_2(2,q)$ полных дуг в $PG(2,q)$, в частности,
\begin{align*}
&t_2(2,q)<\sqrt q\sqrt{3\ln q+\ln\ln q+\ln 3}+\sqrt{\frac q{3\ln q}}+3,\\
&t_2(2,q)<1{,}87\sqrt{q\ln q}.
\end{align*}
Рассмотрены нестандартные типы верхних границ для $t_2(2,q)$, один из которых является новым. Эффективность новых границ проиллюстрирована сравнением с наименьшими известными размерами полных дуг, полученными в недавних работах авторов и в данной статье путем компьютерного поиска в широком диапазоне значений $q$. Отмечена связь рассматриваемых вопросов с так называемым парадоксом дней рождения.
УДК:
621.391.1+519.1
Поступила в редакцию: 19.04.2014 После переработки: 25.08.2014