Олимпиадные задачи и "Бритва Оккама"

[Busy_Beaver]

Уместно ли требовать от "олимпиадника" ("олимпиадницы"), чтобы он (она), решая олимпиадную задачу, выполнил (выполнила) больше, чем требуется в условии этой самой задачи?

Приведу простой пример:
На XII Турнире Городов предлагалась следующая задача (Автор: Фомин С.В.):

Найдите 10 натуральных чисел обладающих тем свойством, что их сумма делится на каждое из них.

(Умолчу в данный момент о том, что автор забыл добавить в условие слово "различных", а стало быть, {1,1,1,1,1,1,1,1,1,1} тоже является решением ).

Вот решение самого автора задачи:
=======================
Заметим, что три числа 1, 2 и 3 обладают тем свойством, что их сумма делится на каждое из них. Рассмотрим теперь числа 1, 2, 3 и 6 (6 = 1 + 2 + 3). Очевидно, что эти четыре числа обладают тем же свойством. Допишем теперь к ним пятое число 1 + 2 + 3 + 6 = 12, шестое — 1 + 2 + 3 + 6 + 12 = 24 и т. д. Таким образом получается искомый набор из десяти чисел 1, 2, 3, 6, 12, 24, 48, 96, 192, 384.

А вот решение моей племяшки:
=======================
{1, 2, 4, 5, 8, 10, 20, 200, 250, 500}.
Иными словами, она, сложив некоторые делители числа 1000, получила сумму, равную 1000. И, заметьте, сделала всё в уме, не пользуясь калькулятором и даже ручкой и бумагой!

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

Хочу услышать мнения участников форума. Какое решение на Ваш взгляд лучше? Что победит: "Бритва Оккама" или глубокое созерцание и обобщение?
Заранее благодарен.

[worm2]

С точки зрения стандартной олимпиады Ваша племянница должна получить за задачу максимальное число баллов, поскольку предъявила корректное решение.
Например, как-то на олимпиаде (правда, по информатике) предлагалась задача, предполагавшая решение, использующее динамическое программирование. Я решил её полным перебором, уложившись (не без труда) в ограничение по времени работы. Понятно, что это прокол организаторов: надо было задать больший объём входных данных, чтобы полный перебор заведомо не укладывался во временные ограничения. Тем не менее, мне начислили максимальный балл по этой задаче.

Однако, Турнир Городов, насколько я знаю — не совсем стандартная олимпиада. Может быть, там могут начислять бонусные баллы за некоторые полезные свойства решения? Тогда эти баллы могут быть присуждены нашедшему общий подход, а нашедшему только частное решение — нет.

[Busy_Beaver]

worm2 в сообщении #349094 писал(а):

С точки зрения стандартной олимпиады Ваша племянница должна получить за задачу максимальное число баллов, поскольку предъявила корректное решение.
Однако, Турнир Городов, насколько я знаю — не совсем стандартная олимпиада.

А в чём, на Ваш взгляд, проявляется "нестандартность" Турнира Городов в сравнении с прочими олимпиадами?
И по ходу ещё вопрос: Какая математическая олимпиада является самой трудной (с точки зрения интеллекта)? И существует ли корреляция между олимпиадными успехами и IQ?

-- Чт сен 02, 2010 15:07:44 --

worm2 в сообщении #349094 писал(а):

Ваша племянница должна получить за задачу максимальное число баллов

Получить баллы она не сможет, так как турнир проходил до её рождения, а задачу эту она решила сегодня

[worm2]

Busy_Beaver писал(а):

А в чём, на Ваш взгляд, проявляется "нестандартность" Турнира Городов в сравнении с прочими олимпиадами?

Для меня в своё время это проявилось в том, что я так и не узнал, сколько баллов получил
Сейчас глянул на сайт — выяснилось, что баллы ставят за 3 наилучшие задачи, что для олимпиад не характерно. Кроме того, там производится выравнивание разных регионов путём введения коэффициентов.

[Busy_Beaver]

worm2 в сообщении #349140 писал(а):

Кроме того, там производится выравнивание разных регионов путём введения коэффициентов.

Думаю, это не совсем справедливо. Если организаторы турнира пытаются выравнять различные регионы, напрашивается вывод о том, что эти организаторы подразумевают "слабость" провинциалов.
Иными словами, если провинциалам дают "фору", это означает, что они слабее.
Или я что-то не так понимаю?

[Руст]

Интересная задача. Обозначим числа $a_1,a_2,...,a_k$, пусть $S_k=a_1+a_2+...+a_k$.
Тогда числа $n_i=\frac{S_k}{a_i}$ натуральные, удовлетворяющие одному условию:

$$(1) \ \ \sum_{i=1}^k \frac{1}{n_i}=1.$$

Упорядочивание $a_1\le a_2\le ...\le a_k$ означает $n_1\ge n_2 ...\ge n_k$.
Очевидно, что взяв произвольное решение $(1)$ легко построить единственное взаимно простое решение
$a_i=\frac{lcm(n_1,n_2,...,n_k)}{n_i}$.
Из решения для k $\{n_i\}$ легко строить решение для k+1 по формуле $\{2n_1,2n_2,...,2n_k,2\}$. Можно так же комбинировать решения из нескольких решений, например $\{2n_1,...,2n_k,2m_1,...,2m_l\}$ из двух решений длины k и l. Вышеприведенное можно рассматривать как сращивание с решением длин k и 1 $(n_1=1)$. Можно найти и производное решение длины kl, взяв набор $\{n_im_j\},i=1,..,k,j=1,...,l$. В общем случае могут появится одинаковые числа в наборе.
Всвязи с этим возникают интересные вопросы:
1) Найти (если есть) решение, когда все $n_i>2$ и разные и $min(n_i)=3$.
2) Можно ли любой набор различных чисел $n_i, i=1,2,...m$ с условием $\sum_i \frac{1}{n_i}<1$ дополнить до набора $k>m$, так чтобы выполнялось (1) и все числа в наборе были разными.

[ИСН]

1) Набор (2,3,6) или делители любого другого совершенного числа. Не помню, есть ли ещё "дикие" решения.
Upd. Ах, >2. Хм. Тогда да, вопрос.
2) Про это что-то было на форуме; чем кончилось, не помню.

-- Пт, 2010-09-03, 01:26 --

Но вывод был вроде довольно обнадёживающий.

[worm2]

Busy_Beaver писал(а):

если провинциалам дают "фору", это означает, что они слабее.
Или я что-то не так понимаю?

В моё время коэффициенты были для разных городов то ли в зависимости от размера города, то ли от числа участников Турнира от этого города. Преимущество имели небольшие города с сильными математическими школами (например, Белорецк). Но это касается целых городов. "Выравниваются" ли как-то коэффициенты для отдельных участников в зависимости от города, я не знаю, не особенно интересовался.

[Sonic86]

Руст писал(а):

1) Найти (если есть) решение, когда все $n_i>2$ и разные и $\min(n_i)=3$.

равносильно $2=\frac{1}{r_1}+...+\frac{1}{r_k}, r_j > 1$ (Правильно? )
А существуют ли разложения $1=\frac{1}{n_1}+...+\frac{1}{n_k}$, где $n_j>1$ и различны, которые получаются не из совершенных чисел?

[ИСН]

Можно сращивать разные решения, по одному разложению расщепляя одно из слагаемых в другом разложении. Тогда вот, скажем, такой вариант: (3,4,6,7,14,28).

[Руст]

Sonic86 в сообщении #349324 писал(а):

Руст писал(а):

1) Найти (если есть) решение, когда все $n_i>2$ и разные и $\min(n_i)=3$.

равносильно $2=\frac{1}{r_1}+...+\frac{1}{r_k}, r_j > 1$ (Правильно? )

нет

Цитата:

А существуют ли разложения $1=\frac{1}{n_1}+...+\frac{1}{n_k}$, где $n_j>1$ и различны, которые получаются не из совершенных чисел?

Приведу свое решение. В различных вариантах встречается чуть более общая задача, когда требуется найти наборы таких натуральных чисел $\{n_i,i=1,...,k\}$, что сумма их обратных величин $\sum_i\frac{1}{n_i}=n_0$ целое. Это соответствует тому,что сумма чисел $S_k=\sum_i a_i$ делится на $a_in_0$ для каждого $i$ и $n_i=\frac{S_k}{a_in_0}$. Тогда $\sum_i\frac{1}{n_i'}=1, \ n_i'=n_in_0.$
Пусть имеется набор различных натуральных чисел $\{n_i\},i=1,2,...m$ и $\sum_i\frac{1}{n_i}<n_0$.
Дополним вначале новыми натуральными числами $n_{m+1},n_{m+2},..,n_l$ так, чтобы разность

$$r_l=\frac{P_l}{Q_l}=n_0-\sum_{i=1}^l\frac{1}{n_i}<\frac{1}{max(n_i,i=1,...,l)}.$$

Этого всегда можно добиться из-за расходимости гармонического ряда. Далее определяем по рекурсии: если $P_k=1$ дополняем набор элементом $n_k=Q_k$ и заканчиваем (уже получено решение). Если $P_i>1$ выбираем $n_i=-[-\frac{Q_i}{P_i}]=[\frac{Q_i}{P_i}]+1.$ Тогда $n_i>max(n_j,j<i)$ и следующий остаток получается $r_{i+1}=r_i-\frac{1}{n_i}=\frac{P_in_i-Q_i}{Q_in_i}=\frac{P_{i+1}}{Q_{i+1}}$. Так как $(P_i,Q_i)=1$ по условию, $P_{i+1}=\frac{P_in_i-Q_i}{gcd(n_i,Q_i}\le\frac{P_i-1}{gcd(n_i,Q_i)}<P_i$,
$Q_{i+1}=\frac{Q_in_i}{gcd(n_i,Q_i)}\ge Q_i$, соответственно $n_{i+1}=-[-\frac{Q_{i+1}}{P_{i+1}}>n_i$. Т.е. новые добавляемые числа будут все большими, и процесс остановится.
Возникает интересный вопрос, будет ли давать этот процесс минимально возможное добавление к исходному (минимально ли $k-m$).
Имеется так же операции перестройки наборов.
1) Набор $(n_1,...,n_i,n_{i+1},...,n_k)$ заменяем на $(n_1,...,n_{i-1},ln_i,...,ln_i,n_{i+1},...,n_k)$ удлиняя набор на $l-1$ элементов.
2) Набор $(n_1,...,n_k)$ заменяем на $(n_1,...,n_{i-1},n_i+1,n_i(n_i+1),n_{i+1},..,n_k)$ удлиняя на 1.
Вопрос: Любое ли решение длины $k>n_0$ получается одним из указанных способов из решений меньшей длины. Например, при $n_0=1$ все решения длины 1 $n_1=1$. Имеется только одно решение длины 2 $(2,2)$ получается соответствующей операцией первого или второго типа из решения длины 1. Имеется 3 решения длины 3: $(3,3,3),(2,4,4),(2,3,6)$ все они получаются применением соответствующих операций из решений меньшей длины.

В Mathlinks встречалась задача: найти все натуральные n, такие что

$$n|\sum_{k=2}^n}k^{\phi(n)}.$$

Легко доказать, что условие эквивалентно следующему:

$$(2) \frac{1}{n}+\sum_{p|n}\frac{1}{p}\in N,$$

т.е. отличается от нашей задачи тем, что все $n_i$ простые за исключением быть может одного.
Определим числа $n_0=1,p_{i+1}=n_i+1,n_{i+1}=n_ip_{i+1}$ определяет решение $n_i$ тогда и только тогда, когда все $p_j,j\le i$ простые. Это аналогично тому, что для последовательности чисел $n_0=1,p_{i+1}=n_i+2,n_{i+1}=n_ip_{i+1}$ можно построить правильный $n_i$ угольник тогда и только тогда, когда все числа Ферма $p_j,j\le i$ простые. И здесь и там простые при $i=0,1,...,4$.
Мне кажется, что (2) имеет и другие решения. Однако, без компьютера их не построишь, получатся большие простые числа. Может кто то осмелится найти другие решения.

[Sonic86]

Руст писал(а):

1) Найти (если есть) решение, когда все $n_i>2$ и разные и $\min (n_i)=3$.

$$ 1=\frac{1}{3}+\frac{1}{6}+\frac{1}{9}+\frac{1}{12}+\frac{1}{15}+\frac{1}{18}+\frac{1}{20}+\frac{1}{21}+\frac{1}{30}+\frac{1}{42}+\frac{1}{60}+\frac{1}{84} $$

Еще такое вроде бы

[Sonic86]

Руст писал(а):

Имеется так же операции перестройки наборов.
1) Набор $(n_1,...,n_i,n_{i+1},...,n_k)$ заменяем на $(n_1,...,n_{i-1},ln_i,...,ln_i,n_{i+1},...,n_k)$ удлиняя набор на $l-1$ элементов.
2) Набор $(n_1,...,n_k)$ заменяем на $(n_1,...,n_{i-1},n_i+1,n_i(n_i+1),n_{i+1},..,n_k)$ удлиняя на 1.
Вопрос: Любое ли решение длины $k>n_0$ получается одним из указанных способов из решений меньшей длины?

А я что-то не понял. Если в решении $(n_1,...,n_k)$ все числа различны, то оно не могло быть получено операцией вида 1 $f_1$, значит оно должно получаться операцией вида 2. А решение было получено операцией вида 2 $f_2$ $\Leftrightarrow n_j = n_i^2-n_i$ для каких-то $i,j$. Рассмотрим решение ИСН:

ИСН писал(а):

Тогда вот, скажем, такой вариант: (3,4,6,7,14,28).

Тогда $f_2^{-1}((3,4,6,7,14,28)) = \{ (2,4,7,14,28)\}$, но предыдущее решение уже не может быть получено операциями $f_1,f_2$. Значит его построить этими операциями нельзя.
Правильно?

[Руст]

Что операциями только видов 1 и 2 нельзя получить все решения я давно понял. Операции 2 надо по крайней мере обобщить
2) Заменяем $n_i$ на два элемента $n_i+d \ (d|n_i), \frac{n_i(n_i+d)}{d}.$

[Sonic86]

Руст писал(а):

В Mathlinks встречалась задача: найти все натуральные n, такие что

$$n|\sum_{k=2}^n}k^{\phi(n)}.$$

Легко доказать, что условие эквивалентно следующему:

$$(2) \frac{1}{n}+\sum_{p|n}\frac{1}{p}\in N$$

<...>
Может кто то осмелится найти другие решения.

Например такое:

$$1=\frac{1}{2 \cdot 3 \cdot 11 \cdot 23 \cdot 31}+\frac{1}{2}+\frac{1}{3}+\frac{1}{11}+\frac{1}{23}+\frac{1}{31}$$

-- Пт сен 17, 2010 10:25:31 --

Других решений с числом простых делителей не больших $5$, кроме Ваших и этого, нету.