2014 dxdy logo

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

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




На страницу Пред.  1 ... 11, 12, 13, 14, 15, 16, 17 ... 67  След.
 
 Re: Prime Sums
Сообщение01.11.2012, 10:39 
Аватара пользователя
http://www.wolframalpha.com/input/?i=%28a%2Fx%29%5E2%2B%28x%2Fb%29%5E2#
Это школьная задачка на нахождение экстремума функции $(\frac ax)^2+(\frac xb)^2$

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 12:54 
Аватара пользователя
whitefox в сообщении #638643 писал(а):
http://www.wolframalpha.com/input/?i=%28a%2Fx%29%5E2%2B%28x%2Fb%29%5E2#
Это школьная задачка на нахождение экстремума функции $(\frac ax)^2+(\frac xb)^2$

And for N=4*k k=1,2,3... you get

x = 1/32 N^2 Sqrt[1024+2048 N^2+903 N^4]

and for N=4*k+2 k=1,2,3...

x = 1/32 Sqrt[2304-2080 N^4-2048 N^6-903 N^8]

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 12:59 
Аватара пользователя
Жаль, что задачу
post636339.html#p636339
так и не решили. Сделал кривой алгоритмик. Случайным способом заполняю подмножества. Затем перестановками чисел, пытаюсь выствить заданные суммы. Если выставить все суммы не удалось, все начинается снова с случайного заполнения. Вроде работает.

Возникла очердная теоретическая проблемка. Что то сразу не соображу.
Даны две строго возрастающие последовательности из n натуральных чисел.
$(a_1,...,a_n)$ $a_i < a_{i+1}$
$(b_1,...,b_n)$ $b_i < b_{i+1}$
Последовательности удовлетворяют условиям:
1) $\sum_{i=1}^{n}{a_i}=\sum_{i=1}^{n}{b_i}$

2) $\sum_{i=1}^{j}{a_i} \le \sum_{i=1}^{j}{b_i}$ для всех j $1 \le j \le n$
Доказать:
$\sum_{i \in I}{a_i} \le \sum_{i \in I}{b_i}$, для всех I. Где I подмножество индексов от 1 до n. $I \subseteq \{1,...,n \}$

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 14:53 
Аватара пользователя
Pavlovsky в сообщении #638701 писал(а):
Даны две строго возрастающие последовательности из n натуральных чисел.
$(a_1,...,a_n)$ $a_i < a_{i+1}$
$(b_1,...,b_n)$ $b_i < b_{i+1}$
Последовательности удовлетворяют условиям:
1) $\sum_{i=1}^{n}{a_i}=\sum_{i=1}^{n}{b_i}$

2) $\sum_{i=1}^{j}{a_i} \le \sum_{i=1}^{j}{b_i}$ для всех j $1 \le j \le n$
Доказать:
$\sum_{i \in I}{a_i} \le \sum_{i \in I}{b_i}$, для всех I. Где I подмножество индексов от 1 до n. $I \subseteq \{1,...,n \}$

В общем случае это неверно.
Пример:
$A=\{1,2,6\}$ $B=\{1,3,5\}$
$1\leqslant 1$
$1+2\leqslant 1+3$
$1+2+6\leqslant 1+3+5$
Для $I=\{n\}$ имеем
$\sum_{i \in I}{a_i} > \sum_{i \in I}{b_i}$

-- 01 ноя 2012, 15:07 --

Herbert Kociemba в сообщении #638698 писал(а):
And for N=4*k k=1,2,3... you get

x = 1/32 N^2 Sqrt[1024+2048 N^2+903 N^4]

and for N=4*k+2 k=1,2,3...

x = 1/32 Sqrt[2304-2080 N^4-2048 N^6-903 N^8]

Интересные формулы. :D
Но вычислить, всё же, проще так: $x=\sqrt{min\cdot max}$
причём для любого N.

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 15:19 
Аватара пользователя
whitefox в сообщении #638754 писал(а):
В общем случае это неверно.


Плохо, доказательная база алгоритмов рассыпается. :-(

Pavlovsky в сообщении #638701 писал(а):
Сделал кривой алгоритмик. Случайным способом заполняю подмножества. Затем перестановками чисел, пытаюсь выствить заданные суммы. Если выставить все суммы не удалось, все начинается снова с случайного заполнения. Вроде работает.


Тоже работает из рук вон плохо. :-(

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 15:31 
Аватара пользователя
Pavlovsky
Если не секрет, откуда у Вас выросли эти задачи?

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 15:49 
Аватара пользователя
Решаю задачу для четных N.
Разбил ее на две стадии.
1)Выставляю зачетные диагонали
2) Выставляю зачетные колонки и строки.

Специфика четных N такая, что на второй стадии, в зачетных колонках и строках не заполненные ячейки принадлежат только одной зачетной линии. Количество свободных ячеек, в каждой линии, приблизительно равно N/4. Числа A1,...Am это заранее определенные простые числа , которые будут суммой зачетных линий. Минус сумма уже заполненных ячеек.

Пример
для N=8 надо числа от 41 до 56 (16 штук) разбросать на 8 множеств по 2 штуки в каждом. Это я сделал легко руками.
для N=10 надо числа от 63 до 89 (26 штук, пропущено число 88) разбросать на 10 множеств в 4-х множествах по 2 числа, в 6-ти множествах по 3 числа. A=(146,166,176,187,209,210,213,214,219,224). Мой кривой алгоритм никак не может решить эту задачу, хотя по всем прикидкам это возможно.

-- Чт ноя 01, 2012 18:05:29 --

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

Есть гипотеза
Для существования разбиения необходимо и достаточно.$\sum_{i \in I}{a_i} \le \sum_{i \in I}{b_i}$, для всех I. Где I подмножество индексов от 1 до n. $I \subseteq \{1,...,n \}$
где $(b_1,...,b_n)$ упорядоченный набор чисел A1,...Am.
$(a_1,...,a_n)$ это суммы подмножеств, если их последовательно заполнять числам из интервала. То есть эта последовательность определяет минимально возможнуые суммы, которыми можно заполнить подмножества.

-- Чт ноя 01, 2012 18:14:42 --

Задача разбиения возникает и на первой стадии. Грубо говоря есть прямоугольник NxM, нужно его заполнить числами от 1 до N*M, так чтобы сумма в колнке i равнялась заданному Ai. Когда прикидывал алгоритмы для нечетных N там тоже эта задача возникает.

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 16:24 
Аватара пользователя
Pavlovsky
Вы меня озадачили ...

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 16:26 
Аватара пользователя
svb в сообщении #638796 писал(а):
Pavlovsky
Вы меня озадачили ...


Чувствую, что иду по сложному пути, но остановиться уже не могу.

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 17:04 
Аватара пользователя
Pavlovsky
Цитата:
Чувствую, что иду по сложному пути, но остановиться уже не могу.
Я получаю схемы "от фонаря", поэтому и ...
Понятно, что для каждой схемы можно можно вычислить количества клеток a[i], где i=0..4 - число вхождений клетки в линии схемы.
Вот случайные наборы a[4],...,a[0] для разных N:

(Оффтоп)

Код:
29: 42,252,253,252,42
28: 98,196,196,196,98
27: 37,217,220,219,36
26: 84,170,169,168,85
    85,168,169,170,84
25: 31,188,187,188,31
24: 72,144,144,144,72
23: 26,159,160,157,27
    27,157,160,159,26
22: 61,120,121,122,60
    60,122,121,120,61
21: 22,132,133,132,22
20: 50,100,100,100,50
19: 18,108,109,108,18
18: 40, 82, 81, 80,41
    41, 80, 81, 82,40
17: 15, 85, 88, 87,14
16: 32, 64, 64, 64,32
15: 11, 68, 67, 68,11
14: 24, 50, 49, 48,25
13:  9, 49, 52, 51, 8
     8, 51, 52, 49, 9
12: 18, 36, 36, 36,18
11:  6, 36, 37, 36, 6
10: 12, 26, 25, 24,13
9:  4, 24, 25, 24, 4
8:  8, 16, 16, 16, 8
7:  2, 15, 16, 13, 3
     2, 16, 13, 16, 2
     3, 13, 16, 15, 2
6:  4, 10,  9,  8, 5
     5,  8,  9, 10, 4
5:  1,  8,  7,  8, 1
Это только для экстремальных схем. Этот эксперимент показывает многообразие различных схем для данного N. Даже для одного набора a[i] существует множество различных схем. Для N>7 экстремальных схем достаточно для решения исходной задачи, но при меньших N этих схем уже недостаточно, в переборный процесс необходимо включать и неэкстремальные схемы. Вот тут могут и понадобиться ваши рассуждения о простых числах, но ... задачу необходимо усложнить :-( Особенно для N=7 :-)

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 17:05 
Аватара пользователя
whitefox в сообщении #638754 писал(а):
Но вычислить, всё же, проще так: $x=\sqrt{\min\cdot \max}$

А минимальное число очков при любом N равно: $2\frac{\min}{\max}$

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 17:25 
Аватара пользователя
svb в сообщении #638822 писал(а):
Я получаю схемы "от фонаря",


А причем поиск схем и моя задача? Схемы я умею находить для любых N. Я решаю задачу построения квадрата по заданной схеме. Что бы пока не заморачиваться с особенностями маленьких N. Решаю задачу для N>=8.

 
 
 
 Re: Prime Sums
Сообщение01.11.2012, 17:36 
Аватара пользователя
Pavlovsky
Цитата:
А причем поиск схем и моя задача?
Я просто пояснил свой "подход", а об остальном задумался :-)

 
 
 
 Re: Prime Sums
Сообщение02.11.2012, 05:28 
Аватара пользователя
Появились группы джентльменов :D с одинаковым набором результатов:

Цитата:
2 Robert Gerbicz 49.995600 10-23-2012 @ 22:11:05
3 Wes Sampson 49.995600 11-02-2012 @ 03:40:31
4 Serg Belyaev 49.994300 10-31-2012 @ 22:12:29
5 Herbert Kociemba 49.994300 11-01-2012 @ 19:44:26

По идее вторая группа вот-вот должна объединиться с первой группой. В идеале все джентльмены будут иметь 50 баллов :wink:
Pavlovsky уже давно озвучил вопрос: сколько будет джентльменов с 50 баллами в конце конкурса? :D
49 баллов с хвостиком сейчас имеют более 20 конкурсантов из 65.

Вообще при взгляде на эти результаты возникает стойкое ощущение, что задача... не очень.
Многие очень быстро её раскололи и почти у рекордных результатов, ну не хватает самую малость.

Пока первое место свободно (dimkadimon не в счёт).
Кто будет первым джентльменом, набравшим 50 баллов при текущих рекордах?
Улучшение рекордов - дело сложное, но вполне возможное, как недавно показал dimkadimon.

-- Пт ноя 02, 2012 06:54:40 --

Pavlovsky в сообщении #638764 писал(а):
Pavlovsky в сообщении #638701 писал(а):
Сделал кривой алгоритмик. Случайным способом заполняю подмножества. Затем перестановками чисел, пытаюсь выствить заданные суммы. Если выставить все суммы не удалось, все начинается снова с случайного заполнения. Вроде работает.


Тоже работает из рук вон плохо. :-(

Pavlovsky
этот "кривой алгоритмик" замечательно работает, если по нему работает естественный интеллект :-)
Именно по этому алгоритму я построила почти все свои решения. Делала это в Ворде, но ещё лучше это делать в Экселе (не умею им пользоваться). В Ворде делала только строки и столбцы, суммы в диагоналях не считала. Прекращала делать квадрат, когда уже оставалось 3-4 строки/столбца не выставлены. Иногда диагонали завершали дело до конца (автоматом), иногда не хватало всего одной суммы, как в приведённом ниже примере для квадрата 28х28. В этом квадрате уже готовы 55 линий.
Делала это шутя, самый большой квадрат 29х29 примерно за полчаса.
Это мой алгоритм "свободных электронов", о котором писала в самом начале.

(Оффтоп)

Вот квадрат 28х28 с 55 готовыми линиями:

Изображение

Замечу: мне ни разу не пришлось начинать всё сначала, все квадраты сделаны с первой попытки.

 
 
 
 Re: Prime Sums
Сообщение02.11.2012, 06:20 
Аватара пользователя
Nataly-Mak в сообщении #638974 писал(а):
Вообще при взгляде на эти результаты возникает стойкое ощущение, что задача... не очень.
Многие очень быстро её раскололи и почти у рекордных результатов, ну не хватает самую малость.


А по мойму задача оказалась вполне неплохой. Имено самую малость набрать сложнее всего. Готов поспорить что 50 баллов будет не так много. Думаю меньше 10ти, а может меньше 5ти.

Nataly-Mak в сообщении #638974 писал(а):
Пока первое место свободно (dimkadimon не в счёт).


Не в счёт в плане призов.

 
 
 [ Сообщений: 1005 ]  На страницу Пред.  1 ... 11, 12, 13, 14, 15, 16, 17 ... 67  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group