2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: Конкурс Изящные Графы
Сообщение31.10.2013, 17:42 
Аватара пользователя


21/02/10
1594
Екатеринбург
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$. Что кажется маловероятным.

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:39 
Основатель
Аватара пользователя


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

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение05.11.2013, 18:28 
Аватара пользователя


21/02/10
1594
Екатеринбург
В этом посте рассмотрим решения вида $(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.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение14.11.2013, 08:10 
Аватара пользователя


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

Гипотеза 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.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение24.11.2013, 00:35 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение24.11.2013, 01:37 


24/11/10
48
dimkadimon в сообщении #791911 писал(а):
Я давно сдался. Работаю над более интересными задачами. Я предложил Ал одну задачку для конкурса. Он сначала ее принял и сказал что сможет сделать конкурс в Январе. Но потом передумал, сказал что у него мало времени.


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

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение08.12.2013, 11:40 
Аватара пользователя


21/02/10
1594
Екатеринбург
Рассмотрим решения вида $(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}$

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение21.12.2013, 14:45 


16/08/05
1146
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

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение22.12.2013, 19:18 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение22.12.2013, 21:26 


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

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение23.12.2013, 06:35 
Аватара пользователя


21/02/10
1594
Екатеринбург
Конкурс закончился. Как и ожидалось, задачу с семидесятилетней историей, решить за три месяца оказалось нереально. Впрочем сам процесс решения задачи оказался познавательным. И может кто то заинтересуется задачей и впишет свое имя в историю!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3, 4

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group