Al Zimmerman - Delacorte Numbers

[dimkadimon]

Pavlovsky в сообщении #926960 писал(а):

У меня уже для N=6 не оптимальное решение. Поэтому экспериментально проверить гипотезу затруднительно. Но мое лучшее решение для N=6 имеет k=9, score=1502. Впрочем это понятно, оно было получено по алгоритму в два этапа.

Для N=4 лучшее решение (оптимальное) имеет k=4, score=240.

Так что доводы в пользу двух-этапного алгоритма есть!

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

Кстати мне кажется алгоритм можно улучшить. Можно разбить второй этап (где мы оптимизируем четвертинки) в несколько маленьких этапов. В каждом маленьком этапе оптимизируем самые крайние места, начиная с углов. Например вот возможный порядок оптимизации для 8x8:

12344321
23455432
34566543
45677654
45677654
34566543
23455432
12344321

[Pavlovsky]

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

Кстати мне кажется алгоритм можно улучшить.

Ну у меня тоже много соображений по этому поводу.

Например.
Будем называть весом числа k:
$\sum\limits_{i \ne k}{nod(i,k)}$

Веса чисел для N=4

(Оффтоп)

12 23
6 17
8 17
16 17
15 16
10 15
4 13
14 13
3 8
5 8
9 8
2 7
7 6
11 0
13 0

Как это использовать, очевидно. Чем выше вес числа тем ближе он должен быть к углам квадрата.

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

[Vitaly12]

Цитата:

Будем называть весом числа k:
$\sum\limits_{i \ne k}{nod(i,k)}$

Веса чисел для N=4

(Оффтоп)

12 23
6 17
8 17
16 17
15 16
10 15
4 13
14 13
3 8
5 8
9 8
2 7
7 6
11 0
13 0

Я не понял, почему, к примеру, у вас для 2 вес 7 а не 14?

[Pavlovsky]

Vitaly12 в сообщении #927841 писал(а):

Я не понял, почему, к примеру, у вас для 2 вес 7 а не 14?

Ой извиняюсь. Я считаю по предложенной WhiteFox методе. НОД уменьшается на единицу.

$\sum\limits_{i \ne k}{(nod(i,k)}-1)$

[Vitaly12]

Цитата:

Я считаю по предложенной WhiteFox методе. НОД уменьшается на единицу.

А как насчет если просто не прибавлять к сумме НОДы равные единице? Результат для сравнения чисел будет тот же, или так хуже?

[dmd]

Квадратность задачи можно развернуть в чисто векторное описание.

Пусть для квадрата $n\times n$ нужно найти вектор $X$ длиной $N=n^2$. Тогда искомая сумма зависит от двух статичных таблиц GCD и DIST размером $N\times N$. Статичных в том смысле, что их не нужно пересчитывать в процессе вычислений и достаточно посчитать в начале.

(код GCD и DIST)

n= 3; N= n^2;

GCD= matrix(N, N, i, j, gcd(i, j));

DIST= matrix(N, N);
for(a=1, N,
 ia= a\n; ja= a%n; if(ja, ia++, ja= n);
 for(b=1, N,
  ib= b\n; jb= b%n; if(jb, ib++, jb= n);
  if(ib > ia || (ia == ib && jb > ja), DIST[a,b]= (ia - ib)^2 + (ja - jb)^2, DIST[a,b]= 0)
));

(GCD и DIST для n=3)

? GCD
%4 =
[1 1 1 1 1 1 1 1 1]
[1 2 1 2 1 2 1 2 1]
[1 1 3 1 1 3 1 1 3]
[1 2 1 4 1 2 1 4 1]
[1 1 1 1 5 1 1 1 1]
[1 2 3 2 1 6 1 2 3]
[1 1 1 1 1 1 7 1 1]
[1 2 1 4 1 2 1 8 1]
[1 1 3 1 1 3 1 1 9]

? DIST
%5 =
[0 1 4 1 2 5 4 5 8]
[0 0 1 2 1 2 5 4 5]
[0 0 0 5 2 1 8 5 4]
[0 0 0 0 1 4 1 2 5]
[0 0 0 0 0 1 2 1 2]
[0 0 0 0 0 0 5 2 1]
[0 0 0 0 0 0 0 1 4]
[0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0]

(GCD и DIST для n=4)

? GCD
%14 =
[1 1 1 1 1 1 1 1 1  1  1  1  1  1  1  1]
[1 2 1 2 1 2 1 2 1  2  1  2  1  2  1  2]
[1 1 3 1 1 3 1 1 3  1  1  3  1  1  3  1]
[1 2 1 4 1 2 1 4 1  2  1  4  1  2  1  4]
[1 1 1 1 5 1 1 1 1  5  1  1  1  1  5  1]
[1 2 3 2 1 6 1 2 3  2  1  6  1  2  3  2]
[1 1 1 1 1 1 7 1 1  1  1  1  1  7  1  1]
[1 2 1 4 1 2 1 8 1  2  1  4  1  2  1  8]
[1 1 3 1 1 3 1 1 9  1  1  3  1  1  3  1]
[1 2 1 2 5 2 1 2 1 10  1  2  1  2  5  2]
[1 1 1 1 1 1 1 1 1  1 11  1  1  1  1  1]
[1 2 3 4 1 6 1 4 3  2  1 12  1  2  3  4]
[1 1 1 1 1 1 1 1 1  1  1  1 13  1  1  1]
[1 2 1 2 1 2 7 2 1  2  1  2  1 14  1  2]
[1 1 3 1 5 3 1 1 3  5  1  3  1  1 15  1]
[1 2 1 4 1 2 1 8 1  2  1  4  1  2  1 16]

? DIST
%15 =
[0 1 4 9  1 2 5 10  4 5 8 13  9 10 13 18]
[0 0 1 4  2 1 2  5  5 4 5  8 10  9 10 13]
[0 0 0 1  5 2 1  2  8 5 4  5 13 10  9 10]
[0 0 0 0 10 5 2  1 13 8 5  4 18 13 10  9]
[0 0 0 0  0 1 4  9  1 2 5 10  4  5  8 13]
[0 0 0 0  0 0 1  4  2 1 2  5  5  4  5  8]
[0 0 0 0  0 0 0  1  5 2 1  2  8  5  4  5]
[0 0 0 0  0 0 0  0 10 5 2  1 13  8  5  4]
[0 0 0 0  0 0 0  0  0 1 4  9  1  2  5 10]
[0 0 0 0  0 0 0  0  0 0 1  4  2  1  2  5]
[0 0 0 0  0 0 0  0  0 0 0  1  5  2  1  2]
[0 0 0 0  0 0 0  0  0 0 0  0 10  5  2  1]
[0 0 0 0  0 0 0  0  0 0 0  0  0  1  4  9]
[0 0 0 0  0 0 0  0  0 0 0  0  0  0  1  4]
[0 0 0 0  0 0 0  0  0 0 0  0  0  0  0  1]
[0 0 0 0  0 0 0  0  0 0 0  0  0  0  0  0]

При этом считать сумму нужно по ненулевому треугольнику матрицы DIST. Количество элементов суммы легко определить для каждого $N$

(кол-во членов суммы)

? n=3;N=n^2;sum(i=1,N-1,i)
%17 = 36
? n=4;N=n^2;sum(i=1,N-1,i)
%18 = 120
? n=5;N=n^2;sum(i=1,N-1,i)
%19 = 300
? n=6;N=n^2;sum(i=1,N-1,i)
%20 = 630

Количество единиц в треугольнике DIST зададут константу (только когда ищем максимум суммы) в искомой сумме, и оно равно (возможно, не уверен) $2(N-n)$. Количество единиц в соответствующем треугольнике матрицы GCD больше, поэтому смотреть нужно на единицы матрицы DIST.

Сама же сумма считается как

sum(i=1,N-1,sum(j=i+1,N,GCD[X[i],X[j]]*DIST[i,j]))

Это включая единицы, т.е. без вычета константы. Можно попытаться посчитать её без единиц с вычетом константы, что несколько сократит вычисления.

Итог. Задача выглядит NP-трудной. Ни веса чисел, ни разбиение квадрата на подквадраты не помогают. Получающиеся оптимумы не соответсвуют действительным. Пытаюсь в "векторной" картинке разглядеть хоть какую-то эвристику, в "квадратной" картине всё выглядит ещё сложнее.

[P.M.D.]

Уже четвертый день сайт конкурса недоступен

[Pavlovsky]

Немного о весовой функции.

Гипотеза. Пусть K число с максимальным весом. Тогда в решении с максимальным числом Делакорта, числа K и K/2 находятся в противоположных углах квадрата.

Примеры.
N=4 числа 16,8
N=5 числа 24,12
N=6 числа 36,18

[dmd]

Pavlovsky

Это понятно. Не понятно другое со второй диагональной парой углов, допустим на примере n=4. Почему в фактическом оптимуме во второй паре углов стоят числа (12,15), а не (12,6)? Казалось бы положить в сумму член 18*6 эффектнее, чем 18*3, но нет же. Почему совокупный вес (12,15) оказался сильнее, чем у пары (12,6)?

[Pavlovsky]

Весовая функция всего лишь эвристика.
12 23
6 17
8 17
16 17
15 16

Число 15 на пятом месте. То есть достаточно хороший кандидат, чтобы поставить его в угол.

-- Пт ноя 14, 2014 15:34:35 --

dmd в сообщении #930805 писал(а):

Почему совокупный вес (12,15) оказался сильнее, чем у пары (12,6)?

Ну и конечно есть повод задуматься. Может как то уточнить весовую функцию или ее применение?

[dimkadimon]

dmd в сообщении #930805 писал(а):

Почему совокупный вес (12,15) оказался сильнее, чем у пары (12,6)?

Не забывайте про другие числа. 12 стоит в углу чтобы быть напротив 4 и 6, а 15 напротив 10. Если 15 заменить на 6, тогда 15 будет ближе к 10 и давать меньше очков (*). Тут все связано и поэтому эвристики не всегда будут работать.

(*) Правда пара (12,6) будет давать больше, но видимо не достаточно больше чтобы покрыть потерю от пары (10,15).

-- 14.11.2014, 20:32 --

Pavlovsky в сообщении #930790 писал(а):

Гипотеза. Пусть K число с максимальным весом. Тогда в решении с максимальным числом Делакорта, числа K и K/2 находятся в противоположных углах квадрата.

Для 9x9 у меня стоят цифры (по часовой стрелке): 80, 36, 60, 72. 40 почти напротив 80. Для 10х10 у меня: 96, 90, 84, 60. 48 почти напротив 96, 42 почти напротив 84, а 45 почти напротив 90. Поэтому есть подозрение что гипотеза не работает.

[whitefox]

Обозначим через $M_k$ множество целых положительных чисел не больших $n^2$ и кратных $k,$ и пусть $x_i,y_i$ обозначают $x$ и $y$ координаты числа $i$ соответственно, а $\bar x_k,\bar y_k$ обозначают средние $x$ и $y$ координаты всех чисел множества $M_k.$ И пусть $\varphi(k),$ как обычно, обозначает функцию Эйлера.

Тогда число Делакорта равно:

$$D=\frac{n^4(n^2-1)}6+\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$

$$D_k=\left\lfloor\frac{n^2}k\right\rfloor\sum\limits_{i\in M_k}\left((x_i-\bar x_k)^2+(y_i-\bar y_k)^2\right)$$

В частности, из этой формулы следует утверждение Pavlovsky

Pavlovsky в сообщении #916827 писал(а):

Для простоты изложения, пусть N=4.
Сформируем группы чисел.
2,4,6,8,10,12,14,16
3,6,9,12,15
4,8,12,16
5,10,15
6,12
7,14
8,16

Утверждение. Если можно заполнить квадрат 4х4 таким образом, что для каждой группы чисел сумма расстояний между ячейками минимально возможная. Тогда такое заполнение является минимально возможным решением.

Также замечу, что согласно данному ранее определению $D^*$

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

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

$$D^*=\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$

Вычислять $D_k$ удобнее по следующей формуле:

$$D_k=\left(\left\lfloor\frac{n^2}k\right\rfloor\sum\limits_{i\in M_k}\left(x^2_i+y^2_i\right)\right)-\left(\left(\sum\limits_{i\in M_k}x_i\right)^2+\left(\sum\limits_{i\in M_k}y_i\right)^2\right)$$

[Yadryara]

whitefox, спасибо. Хотя удивляет сам факт свободного обсуждения конкурсных задач.

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

Тогда число Делакорта равно:

$$D=\frac{n^4(n^2-1)}6+\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$

$$D_k=\left\lfloor\frac{n^2}k\right\rfloor\sum\limits_{i\in M_k}\left((x(i)-\bar x_k)^2+(y(i)-\bar y_k)^2\right)$$

Это верно, хотя Вами и не определён множитель $\varphi(k)$. Впрочем, понятно, что это за птица:

$\varphi(2)=1$
$\varphi(3)=2$
$\varphi(4)=2$
$\varphi(5)=4$
$\varphi(6)=2$
$\varphi(7)=6$
...

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

Вычислять $D_k$ удобнее по следующей формуле:

$$D_k=\left\lfloor\frac{n^2}k\right\rfloor\sum\limits_{i\in M_k}\left(x^2(i)+y^2(i)\right)-\left(\left(\sum\limits_{i\in M_k}x(i)\right)^2+\left(\sum\limits_{i\in M_k}y(i)\right)^2\right)$$

А вот это неверно. Формула не прошла численную проверку. Если не согласны, будем разбираться предметно.

[whitefox]

Yadryara в сообщении #931202 писал(а):

Хотя удивляет сам факт свободного обсуждения конкурсных задач.

У Zimmerman к этому вопросу довольно либеральный подход. Обсуждение конкурсных задач не только не запрещено, но даже приветствуется. Безусловно запрещены только две вещи:

• публикация готовых решений, годных к вводу на конкурс;
• публикация кодов программ поиска таких решений.

При этом можно сообщать полученные значения max и min, будь то правда или нет, а также приводить используемые алгоритмы.

К сожалению, сайт конкурса сейчас не доступен, а то привёл бы соответствующую цитату из правил.

Yadryara в сообщении #931202 писал(а):

хотя Вами и не определён множитель $\varphi(k)$. Впрочем, понятно, что это за птица

Обычно, если определение $\varphi(k)$ не приводится, то под этим понимается тотиента Эйлера. Это обозначение стало уже настолько привычным, что функцию Эйлера часто просто называют фи-функцией. Впрочем, ваше замечание учёл и свой предыдущий пост дополнил.

Yadryara в сообщении #931202 писал(а):

А вот это неверно. Формула не прошла численную проверку. Если не согласны, будем разбираться предметно.

Ведь это формула дисперсии, не так ли?
А потому справедливо общее правило

$$D[X] = M\left[(X -M[X])^2\right]=M[X^2]-\left(M[X]\right)^2$$

[Yadryara]

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

К сожалению, сайт конкурса сейчас не доступен, а то привёл бы соответствующую цитату из правил.

Да не надо, я верю Но не перестаю удивляться. Первый раз с таким сталкиваюсь. Стандартом всевозможных конкурсов является обсуждение после их окончания.

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

Ведь это формула дисперсии, не так ли?
А потому справедливо общее правило

$$D[X] = M\left[(X -M[X])^2\right]=M[X^2]-\left(M[X]\right)^2$$

Я ещё раз перепроверю свои расчёты. Но это будет не быстро.