Prime Sums

[whitefox]

http://www.wolframalpha.com/input/?i=%28a%2Fx%29%5E2%2B%28x%2Fb%29%5E2#
Это школьная задачка на нахождение экстремума функции $(\frac ax)^2+(\frac xb)^2$

[Herbert Kociemba]

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]

[Pavlovsky]

Жаль, что задачу
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 \}$

[whitefox]

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]

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

[Pavlovsky]

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

В общем случае это неверно.

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

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

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

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

[whitefox]

Pavlovsky
Если не секрет, откуда у Вас выросли эти задачи?

[Pavlovsky]

Решаю задачу для четных 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 там тоже эта задача возникает.

[svb]

Pavlovsky
Вы меня озадачили ...

[Pavlovsky]

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

Pavlovsky
Вы меня озадачили ...

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

[svb]

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

[whitefox]

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

Но вычислить, всё же, проще так: $x=\sqrt{\min\cdot \max}$

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

[Pavlovsky]

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

Я получаю схемы "от фонаря",

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

[svb]

Pavlovsky

Цитата:

А причем поиск схем и моя задача?

Я просто пояснил свой "подход", а об остальном задумался

[Nataly-Mak]

Появились группы джентльменов с одинаковым набором результатов:

Цитата:

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 баллов
Pavlovsky уже давно озвучил вопрос: сколько будет джентльменов с 50 баллами в конце конкурса?
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 готовыми линиями:

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

[dimkadimon]

Nataly-Mak в сообщении #638974 писал(а):

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

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

Nataly-Mak в сообщении #638974 писал(а):

Пока первое место свободно (dimkadimon не в счёт).

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