Конкурс Изящные Графы

[Pavlovsky]

svb в сообщении #777148 писал(а):

Теорема 1. Пусть база $.a_1 .a_2 ....a_k .x/s.b_1 ....b_m .$ множества $H_s = \left( {0,1,...,L} \right)$ удовлетворяет условиям:
1. $x > a_i$ , $x > b_i$ ,
2. $H_s = def\left( {.a_1 ....a_k .x/s.} \right)\bigcup {def\left( {.x/s.b_1 ....b_m .} \right)}$,
тогда множество $.a_1 .a_2 ....a_k .x/\left( {s + 1} \right).b_1 ....b_m .$ является базой множества $H_{s + 1} = \left( {0,1,...,L + x} \right)$. Кроме того $\left( {0,1,...,x - 1} \right) \in def\left( {.a_1 ....a_k .} \right)\bigcup {def\left( {.b_1 ....b_m .} \right)} $

Рассмотрим для начала решения вида $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$. Где:
1) $x>a_i $ и $x>b_i$.
2) $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$ является решением для всех $s \ge 0$.

Утверждение 1. Для i=[1,k] и j=[1,m], суммы вида $\sum_{l=i}^{k}{a_l}$ и $\sum_{l=1}^{j}{b_l}$ должны содержать остатки по модулю x от 1 до x-1.

Следствие 1. Выполняться неравенство $k+m \ge x-1$.

Гипотеза 1. Для оптимального решения выполняется равенство $k+m=x-1$.
Обоснование гипотезы.

Паттерн Вихмана (WW(r,s)=1:r;r+1; (2r+1):r; (4r+3):s; (2r+2):(r+1); 1:r) удовлетворяет этому условию.
r+1+r+r+1+r=(4r+3)-1.

Рассмотрим два решения вида $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$ , $(r_1,R_1)$ и $(r_2,R_2)$, где $r_1$,$r_2$ количество элементов a,b; $R_1$,$R_2$ сумма элементов a,b.
Пусть $r_1=r_2$ и $R_1>R_2$. Тогда первое решение лучше (оптимальнее) чем второе.
Пусть $r_1<r_2$ и $R_1<R_2$. Рассмотрим эти решения с одинаковым числом элементов S.
$R_1+(S-r_1)x$ и $R_2+(S-r_2)x$. $R_1+(S-r_1)x - R_2-(S-r_2)x= R_1-R_2 + (r_2-r_1)x$
Чтоб бы второе решение было лучше первого необходимо: $R_1 + (r_2-r_1)x < R_2$. Учитывая что $x>a_i$ и $x>b_i$, что бы второе решение оказалось лучше первого оно должно быть лучше как минимум на $(r_2-r_1)x$. Что кажется маловероятным.

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

[Pavlovsky]

В этом посте рассмотрим решения вида $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$. Где:
1) $x>a_i $ и $x>b_i$.
2) $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$ является решением для всех $s \ge 0$.
3) $k+m=x-1$

Утверждение 2. Элементы $(a_1,a_2,...,a_k)$ и $(b_1,b_2,...b_m)$ можно объединить в множества $A_1,A_2,...,A_t$ $B_1,B_2,...,B_t$ так, что решение можно представить в виде: $(A_1,A_2,...,A_t,x:s,B_1,B_2,...,B_t)$ так что
1) для i=[1,t-1] $Sum(A_{i+1})+Sum(B_i)=x$. Где $Sum(A)$ сумма чисел принадлежащих множеству A.
2) $Sum(A_1)+Sum(B_t) < x$.
3) Множества $A_i$ и $B_i$, не могут быть пустыми, кроме множеств $A_1$ и $B_t$

Доказательство. Пусть s достаточно большое, тогда сумма x(s+1) будет выглядеть так $A_t,x:s,B_1$. Пункт 3) следует из $k+m=x-1$.

Гипотеза 2. Оптимальное решение имеет вид $(a_1,...,y:t,x:s,z:t,...b_m)$, где y+z=x.
Обоснование гипотезы. Чем меньше элементов $(a_1,a_2,...,a_k)$ и $(b_1,b_2,...b_m)$ в каждом множестве $A2,...,A_t B_1,B_2,...B_{t-1}$, тем больше получится сумма решения. В идеале в каждом объединении множестве $A2,...,A_t B_1,B_2,...B_{t-1}$ содержится один элемент. То есть $A_t= \{a_k\}$, $B_1=\{b_1\}$ и так далее.

Гипотеза 3. y,z взаимнопростые.

Гипотеза 4. В оптимальном решении разность |z-y| минимальна. То есть в оптимальном решении z=y+1.

[Pavlovsky]

Похоже все уже сдались? Я вяло, но продолжаю работать над задачей, без всяких надежд на успех, так просто согреться.
Для небольшого подъема интереса к задаче выбрасываю очередную порцию гипотез.

Гипотеза 5. Для x вида x=4r+3, оптимальным является паттерн Вихмана .

Задача 1. Найти оптимальные патерны для x вида x=4r и x=4r+1.

Гипотеза 6. Для x вида x=4r+2 хорошего решения не существует.
Обоснование гипотезы.
1) z=2r,y=2r+2 оба числа четные, значит не взаимнопростые, что противоречит гипотезе 3.
2) z=2r-1,y=2r+3, y-z=4, что многовато для гипотезы 4.

[dimkadimon]

Я давно сдался. Работаю над более интересными задачами. Я предложил Ал одну задачку для конкурса. Он сначала ее принял и сказал что сможет сделать конкурс в Январе. Но потом передумал, сказал что у него мало времени.

[Vitaly12]

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

Я давно сдался. Работаю над более интересными задачами. Я предложил Ал одну задачку для конкурса. Он сначала ее принял и сказал что сможет сделать конкурс в Январе. Но потом передумал, сказал что у него мало времени.

Так может Вы организуете конкурс, или хоть подкиньте задачку, а то скучно стало

[Pavlovsky]

Рассмотрим решения вида $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$. Где:
1) $x>a_i $ и $x>b_i$.
2) $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$ является решением для всех $s \ge 0$.

Утверждение 3. Через F() обозначим количество ребер в изящном графе для решения $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$. Тогда выполняется неравенство:
$F() \le x*s+k*m+k+m$.

Утверждение 4. Если выполняется k+m=x-1. Тогда
$F(x,s) \le x*s+\frac{x^2+2*x-3}{4}$

Утверждение 5 (гипотеза 5). Для x вида x=4r+3, оптимальным является паттерн Вихмана .
Доказательство. Для патерна Вихмана (WW(r,s)=1:r;r+1; (2r+1):r; (4r+3):s; (2r+2):(r+1); 1:r)
$F(x=4r+3,s) =x*s+ \frac{x^2+2*x-3}{4}$

[dmd]

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

Утверждение 3. Через F() обозначим количество ребер в изящном графе для решения $(a_1,a_2,...,a_k,x:s,b_1,b_2,...b_m)$. Тогда выполняется неравенство:
$F() \le x*s+k*m+k+m$.

Утверждение 4. Если выполняется k+m=x-1. Тогда
$F(x,s) \le x*s+\frac{x^2+2*x-3}{4}$

А можно объяснить, как получаются эти два выражения?



Если Утверждение 4 не изменится от формы $x$, то для $x=4r+1$ у некоторых простых теоретический максимум становится чуть выше значений паттерна Вихмана (на 3 единицы).

(тест)

glgt()=
{
forprime(p=3,100,
 M= 0; 
 for(r=1,p,
  x=4*r+1;
  for(s=1,p,
   y=s+x;
   if(y==p,
    L=x*s+(x^2+2*x-3)\4;
    if(L>M, M= L)
   )
  )
 );
 print(p,"    ",M)
)
};

3    0
5    0
7    18
11    42
13    60
17    100
19    126
23    182
29    288
31    330
37    468
41    572
43    630
47    750
53    952
59    1178
61    1260
67    1518
71    1702
73    1800
79    2106
83    2322
89    2668
97    3168

[Pavlovsky]

Утверждение 4 является следствием утверждения 3. Для k+m=x-1 и k=m.
В своем доказательстве утверждения 4 я увы нашел ошибку. Так что утверждения 3 и 4 теперь имеют статус гипотез.

Насчет ваших рассуждений, я рассуждал аналогично. Почти до самого конца имел слабую надежду найти решение лучшее чем паттерн Вихмана. Но увы...

[dmd]

В любом случае задача получилась и красивая, и тяжёлая, и.. нерешённая! Оптимальность Вихмана так и осталась неопределённой.

[Pavlovsky]

Конкурс закончился. Как и ожидалось, задачу с семидесятилетней историей, решить за три месяца оказалось нереально. Впрочем сам процесс решения задачи оказался познавательным. И может кто то заинтересуется задачей и впишет свое имя в историю!