Al Zimmerman - Delacorte Numbers

[whitefox]

Pavlovsky
Мне кажется, что ваше условие не является достаточным. Более того, есть сомнение и в его необходимости.

[Pavlovsky]

Если честно, жалко тратить время на подробное доказательство. Но утверждение истинно на 146%.

Естественно о необходимости не идет речи. Если описанного в утверждении заполнения не существует, тогда утверждение дает нижнюю оценку для числа Делакорта, ну и приближенный алгоритм. Для N=3,4,5 такое заполнение существует. Для N>=6, такое заполнение не существует. Группы чисел начинающиеся с 2,3,5,7,11 уложить оптимальным образом нельзя.

[dimkadimon]

Цитата:

То есть пары с $\gcd(a,b)=1$ можно вставлять в последнюю очередь в произвольном порядке. В частности, это верно для простого $a>\frac{N^2}2$ и произвольного $b.$

Это утверждение не верно. Вот контра-пример:

1)
оценка без пар gcd(a,b)=1: 78
оценка со всеми парами: 156
(4,2,7),
(3,9,8),
(1,5,6)

2)
оценка без пар gcd(a,b)=1: 80
оценка со всеми парами: 153
(4,8,7),
(3,9,1),
(2,5,6)

У 1) оценка со всеми парами больше, а у 2) оценка без пар gcd(a,b)=1 больше! Значит не достаточно оптимизировать оценку без пар.

[Pavlovsky]

$\mathrm{distance}^2(a, b)$

Забавная метрика. Три ячейки в ряд. Расстояние между соседними ячейками 1, а между крайними 4. 1+1=4?!

Свойство. Число Делакорта можно представить как сумму D=Dx+Dy. Где Dx в качестве растояния берется квадрат разности координат ячеек по оси x, а Dy по оси y.

[whitefox]

dimkadimon
Вы не правильно произвели оценку без пар $\gcd(a,b)=1$
Посмотрите, пожалуйста, моё определение числа $D^*$

whitefox в сообщении #916612 писал(а):

Определим для каждой пары $(a,b):\quad D^*_{a,b}=\mathrm{distance}^2(a, b)$, и $D^*$ как разность между числом Делакорта $D$ и суммой всех $D^*_{a,b}.$

Иными словами для правильного подсчета $D^*$ нужно $\gcd(a,b)$ уменьшить на единицу.

Получим в случае 1) 48 и в случае 2) 45. Что и подверждает моё утверждение

whitefox в сообщении #916612 писал(а):

Утверждение: $D$ максимально (минимально) тогда и только тогда, когда максимально (минимально) $D^*.$

Которое верно ввиду того, что сумма всех $D^*_{a,b}$ является константой и не зависит от перестановки элементов квадрата.

[dimkadimon]

whitefox в сообщении #916964 писал(а):

dimkadimon
Вы не правильно произвели оценку без пар $\gcd(a,b)=1$
Посмотрите, пожалуйста, моё определение числа $D'$

whitefox в сообщении #916612 писал(а):

Определим $D'_{a,b}=\mathrm{distance}^2(a, b)$ и $D'$ как разность между числом Делакорта $D$ и суммой всех $D'_{a,b}.$

Иными словами для правильного подсчета $D'$ нужно $\gcd(a,b)$ уменьшить на единицу.

Получим в случае 1) 48 и в случае 2) 45. Что и подверждает моё утверждение

whitefox в сообщении #916612 писал(а):

Утверждение: $D$ максимально (минимально) тогда и только тогда, когда максимально (минимально) $D'.$

Которое верно ввиду того, что сумма всех $D'_{a,b}$ является константой и не зависит от перестановки элементов квадрата.

Да вы совершено правы. Оказывается доказательство леммы очень простое.

Определим D'ab=(gcd(a,b)-K)*dist^2(a,b), для какой то константы К.

Тогда, D'ab=gcd(a,b)*dist^2(a,b) - K*dist^2(a,b) = Dab - K*dist^2(a,b). D'=D - K*sum(dist^2(a,b)). Значит D' и D отличаются всего константой, которая не зависит от расположения элементов. В лемме мы используем K=1, при этом убираются все пары с gcd(a,b)=1. Кажется так?

[whitefox]

dimkadimon в сообщении #917148 писал(а):

Определим D'ab=(gcd(a,b)-K)*dist^2(a,b), для какой то константы К.

Тогда, D'ab=gcd(a,b)*dist^2(a,b) - K*dist^2(a,b) = Dab - K*dist^2(a,b). D'=D - K*sum(dist^2(a,b)). Значит D' и D отличаются всего константой, которая не зависит от расположения элементов. В лемме мы используем K=1, при этом убираются все пары с gcd(a,b)=1. Кажется так?

Верно

(Только не забывайте про $\TeX$)

А то тема отправится в карантин.

$D'_{ab}=\gcd(a,b)\cdot\mathrm{dist}^2(a,b)-K\cdot\mathrm{dist}^2(a,b)=D_{ab}-K\cdot\mathrm{dist}^2(a,b)$

$D'_{ab}=\gcd(a,b)\cdot\mathrm{dist}^2(a,b)-K\cdot\mathrm{dist}^2(a,b)=D_{ab}-K\cdot\mathrm{dist}^2(a,b)$

[Toucan]

dimkadimon, замечание за неиспользование $\TeX$ при наборе формул.

[dimkadimon]

Toucan в сообщении #917352 писал(а):

dimkadimon, замечание за неиспользование $\TeX$ при наборе формул.

Простите, больше не буду.

Интересный момент, для 6х6 можно не обменивать цифры 5 и 25 - оценка не изменится. Кто знает почему? ;)

[whitefox]

При обмене 5 и 25 $D_{5,25}$ не изменится, а для всех $1\leqslant b\leqslant36,b\ne25\quad\gcd(5,b)=\gcd(25,b)$

[dimkadimon]

whitefox в сообщении #917572 писал(а):

При обмене 5 и 25 $D_{5,25}$ не изменится, а для всех $1\leqslant b\leqslant36,b\ne25\quad\gcd(5,b)=\gcd(25,b)$

Правильно! Отсюда Лемма 2: Eсли $\gcd(a,c)=\gcd(b,c), ~\forall c<=N^2, a \neq b$ тогда при обмене а и b оценка решения не изменится. Вполне полезная лемма. Она работает для обмена простой $p$ с $p^2$, если $2p^2>N^2$. Также она работает для простых $p>N^2/2$.

[Pavlovsky]

Пусть $p$ простое; $p^k \le \frac{N^2}{2}$; $p^{k+1}>\frac{N^2}{2}$. Тогда в любом решении их можно менять местами.

Пример. N=4, числа 8 и 16 можно менять местами.

[Miklucha]

dimkadimon

Я попробовал составить алгоритм для поставленной задачи и начал с n=5, т.к. n=3 и n=4 решаются в лоб. После практически мгновенного счета получил немногим более 6000 тысяч баллов. Не подскажите, имеет ли смысл с таким результатом регистрироваться на конкурсе?

[P.M.D.]

Если "немногим более" это 100-200 пунктов, то имеет.

[dimkadimon]

Miklucha в сообщении #919155 писал(а):

dimkadimon

Я попробовал составить алгоритм для поставленной задачи и начал с n=5, т.к. n=3 и n=4 решаются в лоб. После практически мгновенного счета получил немногим более 6000 тысяч баллов. Не подскажите, имеет ли смысл с таким результатом регистрироваться на конкурсе?

Ну конечно есть смысл участвовать! Ваш результат близок к оптимальному. Даже если он был не близок, всегда можно его улучшить. В этом конкурсе участвуют лучшие из лучших, поэтому это хороший шанс проверить свои способности.

-- 15.10.2014, 21:37 --

Появился интересный вопрос. Можно ли взять хорошее максимальное решение и превратить его в хорошее минимальное решение (или наоборот)?

Моя первая попытка в этом не очень сработала:

1. Я взял максимальное решение
2. Посчитал сколько баллов имеет каждая клетка
3. Сортировал клетки по баллам. $[S_i],~S_i>=S_{i+1}$.
4. Обменял местами самые "прибыльные" клетки с самыми "неприбыльными". То есть меняем $S_i$ на $S_{n-i}$ для всех $i<n/2$.

Получилось неплохое минимальное решение, но оно далеко от хорошего.