Режем торт

[sng1]

Чтобы добить, осталось вариант с несократимой дробью со знаменателем больше $N!$ выложить.

[12d3]

Зато вроде как получилось доказать, что для $N=7,\,N=8$ получены действительно минимумы. Чуть позже напишу подробно.

[worm2]

Пробую зайти с другой стороны.
Пусть куски пронумерованы по возрастанию: $x_1, x_2, ..., x_m$.

На первом этапе выпишем всевозможные системы уравнений для разбиения на равные части. Для $n=8$ это будут разбиения на на 8, 7, 6 и 5 равных частей, дающих 4 группы из 7+6+5+4 = 22 уравнений.
Например, для решения из 16 кусков для $n=8$ первые 7 уравнений будут такими:

$$x_1+x_{16} = x_2+x_{15} = x_3+x_{14} = x_4+x_{13} = x_5+x_{12} = x_6+x_{11} = x_7+x_{10}=x_8+x_9$$

Вторые 6 уравнений:

$$x_1+x_2+x_{14} = x_3+x_5+x_{10} = x_4+x_{16} = x_6+x_{15} = x_7+x_{13} = x_8+x_{12} = x_9+x_{11}$$

(дальше не буду выписывать, надеюсь, понятно).
На этом этапе нашей задачей будет перебрать всевозможные такие системы уравнений, стараясь отсечь как можно больше бесперспективных вариантов. Например, если в системе попались уравнения $x_1+x_3=x_2+x_4$, то её можно смело выкинуть, так как куски идут по возрастанию (даже если $x_1=x_2=x_3=x_4$, ничто нам не мешает записать то же уравнение как $x_1+x_4=x_2+x_3$). Далее, для разбиений на $k<n$ частей любая $1/k$-я часть будет состоять минимум из двух кусков (уравнения вида $x_{16}=x_5+x_7$ исключаются).
Здесь мы ещё уравнения не решаем, поэтому выгодно записывать их более компактно, как собственно разбиения:
1234567887654321 — для первой группы уравнений (разбиение на 8 частей), назовём его 8-разбиением.
1123245672765143 — для второй группы уравнений (разбиение на 7 частей), назовём его 7-разбиением, и т.д..
и перебирать символьные строки по определённым правилам.
Я пока дошёл только до этого этапа, и то для разбиений не более чем на 7 частей из не более чем 13 кусков. Я сконцентрировался на 7 частях и 13 кусках, дальше будет только про этот вариант.
После указанных оптимизаций у меня получилось 740 возможных 7-разбиений тринадцати кусков, 6-разбиений — 87, 5-разбиений — 11972 и 4-разбиений — 54473. Пока что слишком много, чтобы перебирать их всевозможные сочетания, поэтому нужен дополнительный этап оптимизации.

На втором этапе планируется группировать найденные $k$-разбиения друг с другом, сначала по парам, жадно ища противоречия. Например, 5-разбиение 1234441221553 несовместимо с 6-разбиением 1123455514326, так как выделенный набор 444 весит меньше, чем выделенный набор 555 (в силу того, что куски идут по возрастанию), хотя первый составляет пятую часть торта, а второй — шестую. Затем группируем по тройкам, и т.д, пока не получим полные наборы разбиений, кажущиеся непротиворечивыми. Совершенно непонятно, сколько можно будет выгадать на такой оптимизации. Если не слишком много, то придётся начинать решать системы уравнений совместно друг с другом, не сгенерировав предварительно всё множество систем.

На третьем этапе вспомним, что разбиения задают системы уравнений и проверяем, какие системы имеют решение. Для этого последнее уравнение, определяющее, что сумма кусков равна единице, мы не привлекаем, а просто ищем те системы из 22-уравнений с 13-ю неизвестными, у которых ранг меньше максимального (то есть 12). Здесь тоже возможна оптимизация, мы ведь можем сначала проверить систему из первых 6+5+4=15 уравнений (не более миллиарда случаев), и если у неё ранг уже 13, то дальше искать нет смысла.

Преимущество такого подхода в том, что он действительно перебирает всевозможные варианты разбиений и позволяет строго доказать, что решения нет (ну, если мы в погоне за оптимизацией перебора не отсекли лишнего), или, если оно есть, находит его.

[12d3]

Доказательство того, что для $N=7$ нельзя разрезать на 13 кусков.
Я следовал идее решения более простой задачки.
Предположим, что можно разрезать на 13 кусков. Весь торт считаем за 420. При делении на семерых будет по 60 каждому, на шестерых - по 70.
Строим двудольный граф, как в решении задачки по ссылке, для разбиения на 7 и на 6 гостей. Выяснять, можно ли разбить на 5 и на 4 гостей, будем потом.
Во-первых, граф связен, во-вторых в нем есть цикл, и убрав одно ребро из цикла, получим дерево. Пусть убрано ребро весом $x$ (т.е. размер куска, соответствующего этому ребру), в процедуре убирания к $n$ ребрам добавится $x$, а у $n-1$ ребер отнимется $x$. После убирания останется граф-дерево. Утверждение следующее - независимо от вида этого графа, веса всех ребер кратны 10. Доказательство этого факта не очень строгое: мы изначально знаем сумму весов всех ребер, входящих в вершину - она либо 60, либо 70. Если вершина степени один, то мы сразу знаем вес ребра, входящего в эту вершину. Если мы знаем веса всех ребер, входящих в вершину, кроме одного, то мы можем узнать вес этого неизвестного ребра. Поскольку граф - дерево, не может быть такой ситуации, что в каждой вершине либо 0, либо не менее двух неизвестных ребер. В процессе вычисления весов ребер мы производим только сложения вычитания чисел, кратных 10, поэтому веса всех ребер будут кратны 10.
Теперь вернемся к нашему старому графу с 13 ребрами, который был до убирания одного ребра. В этом графе веса ребер равны либо $10k_i$, либо $10k_i+x$, либо $10k_i-x$, причем вторых и третьих поровну. Будем считать, что значения $k_i$ фиксированы, а $x$ -переменная, которую нужно подобрать, чтобы существовало разбиение на пятерых и на четверых.
Попробуем сначала разделить эти куски на пятерых. Пусть сумма весов ребер на каждого из 5 гостей равна $10a_j+b_jx=84,\,\, 1 \le j \le 5$. Сумма всех $b_j$ равна нулю, сумма модулей $b_j$ не превышает 12. Из этих уравнений следует, что $\frac{84-10a_j}{b_j} = \frac{84-10a_k}{b_k},\,\, \forall j,k $.
$84(b_j-b_k) = 10(a_kb_j-a_jb_k) \Rightarrow b_j-b_k \vdots 5 \, \forall j,k$.
Итак, у нас про $b_j$ известно следующее: $\Sigma b_j = 0,\,\,\Sigma |b_j| \le 12$, они все сравнимы по модулю 5, и они все ненулевые (иначе получится неверное равенство $10a_j=84$). Всего возможны 4 варианта наборов $b_j$, удовлетворяющих всем этим условиям: $(1,1,1,1-4),\,\,(-1,-1,-1,-1,4),\,\,(2,2,2,-3,-3),\,\,(-2,-2,-2,3,3)$. Поскольку из равенства $10a_j+b_jx=84$ следует, что $b_jx$ - целое и даже четное, то во всех четырех вариантах можно получить, что $x$ - целое и четное.
Теперь попробуем разделить на четверых. Совершенно аналогично, каждый из четырех получит по $10c_j+d_jx=105,\,\, 1 \le j \le 4$. Но в каждом равенстве сумма слева четная, а справа нечетная. Противоречие. Т.о. доказано, что на 13 разрезать нельзя.
Для $N=8$ рассуждения аналогичные, с тем лишь отличием, что $x$ может оказаться полуцелым, но числитель его будет обязательно кратен 5, что также приводит к противоречию.

[Skeptic]

12d3, надо обосновать, почему берётся часть длиной 60 единиц. При этой максимальной длине одной части торт для 7 человек надо разрезать не меньше, чем на 18 частей. Так что 13 частей заведомо не проходят. Как было показано, при длине 59 достаточно 14 частей.

[Null]

12d3,для $N=7$ похоже на правду. Для $N=8$ многовато вариантов $b_i$ получается.

Skeptic в сообщении #1079030 писал(а):

12d3, надо обосновать, почему берётся часть длиной 60 единиц. При этой максимальной длине одной части торт для 7 человек надо разрезать не меньше, чем на 18 частей. Так что 13 частей заведомо не проходят. Как было показано, при длине 59 достаточно 14 частей.

Он ни где не берет в исходном разрезании часть 60.

[Sender]

Skeptic в сообщении #1079030 писал(а):

12d3, надо обосновать, почему берётся часть длиной 60 единиц.

В принципе, доказательство не изменится, если торт взять объёмом $1$, а $60$ и $70$ заменить на $\frac{1}{7}$ и $\frac{1}{6}$ соответственно.

[Null]

Если добавлять не 1 ребро а 2 то все веса равны $\frac{a_i}{N(N-1)}+k_ix+l_iy$, где все $k_i,l_i \in\{-1,0,1\}$

[Sender]

12d3 в сообщении #1079021 писал(а):

$84(b_j-b_k) = 10(a_kb_j-a_jb_k) \Rightarrow b_j-b_k \vdots 5 \, \forall j,k$.

При условии $F(n)=2n-1$ это соотношение можно обобщить на произвольные $n>8$, тогда оно примет вид
$n(n-1)(b_j-b_k) = (n-2)(a_kb_j-a_jb_k) \, \forall j,k$
В силу взаимной простоты $n-1$ и $n-2$ отсюда следует, что

$$n(b_j-b_k) \vdots (n-2) \, \forall j,k \eqno{(1)}$$

При чётных $n$ имеет место $2(b_j-b_k) \vdots (n-2) \, \forall j,k,$
при нечётных - $(b_j-b_k) \vdots (n-2) \, \forall j,k.$
Исключим из рассмотрения нулевые $b_i$, тривиальным образом ведущие к противоречию.
Поскольку каждая из $n-2$ частей состоит не менее, чем из $2$-х кусков, а всего кусков, содержащих $x$, не более $2n-2$, $\forall i \, |b_i|\leqslant 4 $.
При этом, если для некоторого $i_0$ $|b_{i_0}|= 4$, то для всех остальных $i$ $|b_i|\leqslant 2$. Далее, при $n\geqslant 8$ найдутся $b_j$ одного знака с $b_{i_0}$, т.е. $0<|b_{i_0}-b_j| \leqslant 3.$
При любом разрезании найдутся пары $b_i \neq b_j$, поскольку $\forall i \,b_i \neq 0 $ и $\sum\limits_{i}b_i=0.$
Таким образом, при $n\geqslant 8$ всегда найдутся $i,j$ такие, что $0<|b_i-b_j| \leqslant 5$
Возвращаясь к $(1)$, получим, что при $n>8$ $F(n)\geqslant 2n$, кроме, быть может, $n \in \{10,12\}.$

[Null]

Можно брать не только $n-2$ но и меньшие числа.
Ваше рассуждения ведь для деления только на $N,N-1,N-2$ частей? другие вроде не используются.

[Sender]

Null в сообщении #1079203 писал(а):

Можно брать не только $n-2$ но и меньшие числа.

Да, но тогда ухудшится верхняя оценка на $|b_i|$ - я пока лучше применения принципа Дирихле ничего не вижу.

[Null]

зато для $n=10$ ,будет делимость на $7$, а не на $4$.

[Sender]

Хм, тогда надо доказать, что среди $7$ ненулевых целых чисел, $3$ из которых по модулю не превосходят $2$, с суммой модулей не более $18$, дающих в сумме $0$, найдутся $2$ различных числа, разность которых по модулю не превосходит $6$. Пойду-ка я лучше спать.

[Null]

Маленькие $b_i$ Дают сильное ограничение на $x$.
Например у вас:

12d3 в сообщении #1079021 писал(а):

то во всех четырех вариантах можно получить, что $x$ - целое и четное.

А это мешает разделить торт на другие количества частей.

[Sender]

Null в сообщении #1079322 писал(а):

Маленькие $b_i$ Дают сильное ограничение на $x$.

Да, действительно. При разбиении $2n-1$ кусков на $n-2$ и на $n-3$ частей при $n >8$ найдутся $b_i$, по модулю не превышающие $2$.
Если при $n=10$ взять объём торта равным $2520$, при разбиении на $8$ частей $b_jx=315-28a_j$, что означает нечётность либо полуцелость $x$.
При разбиении на $7$ частей имеем $b_jx=360-28a_j$. Правая часть делится на $4$, значит, $x$-чётное.
Если при $n=12$ взять объём торта равным $27720$, при разбиении на $10$ частей $b_jx=2772-210a_j$. Значит, $x$ не делится на $5$.
При разбиении на $9$ частей имеем $b_jx=3080-210a_j$. Правая часть делится на $10$, значит, $x$-целое и $x\vdots 5$.

-- Пт дек 04, 2015 10:11:37 --

Таким образом, можно считать доказанным утверждение:
При $n \geqslant 7$ $F(n)\geqslant 2n.$

-- Пт дек 04, 2015 10:38:51 --

Нашёл ошибку в сообщении #1079191. Возможен случай, когда для некоторого $i_0$ $|b_{i_0}|=5$. Но при $n>8$ найдутся $b_j$ одного знака с $b_{i_0}$, так что $0<|b_{i_0}-b_j|\leqslant 4.$