Олимпиада НГУ-2013

[bot]

EtCetera в сообщении #780977 писал(а):

Но почему именно 600?

Первое круглое после 512.

ewert в сообщении #781072 писал(а):

Как-то не шибко иммер элегант

Достаточно заметить, что инъективная непрерывная функция монотонна.

Oleg Zubelevich в сообщении #781105 писал(а):

Я бы предложил ТС такую задачу

Мне порешать или студентам дать?

[TOTAL]

bot в сообщении #780674 писал(а):

4. У мухи один носок и одна туфелька на каждую из её шести ножек. Сколько различных порядков обувания возможно, если считать, что муха никогда не наденет туфельку на голую ногу, а носок - поверх туфельки?

Условие не запрещает мухе надеть носок поверх носка и туфельку поверх туфельки, т.е. сразу все носки и туфельки на левую переднюю ногу?

[bot]

Да, это упущение. Впрочем, носок поверх носка ещё можно одеть, а туфельку поверх туфельки вряд ли.

[iifat]

ewert в сообщении #781072 писал(а):

Попробуем добить.

bot в сообщении #780674 писал(а):

2. Существует ли непрерывная функция $f:\mathbb R\to\mathbb R$, удовлетворяющая тождеству

$$f(f(x))=e^{-x}\, ?$$

Моё с другого форума.
$f(x_1)=f(x_2)\Rightarrow f(f(x_1))=f(f(x_2))$, что неверно. Значит, $f(x)$ монотонна на всей числовой оси. Если она монотонно возрастает, то $f(f(x))$ возрастает; если она убывает, $f(f(x))$ всё равно возрастает. Противоречие.

[TOTAL]

(Оффтоп)

bot в сообщении #781140 писал(а):

Да, это упущение. Впрочем, носок поверх носка ещё можно одеть, а туфельку поверх туфельки вряд ли.

Исправленный вариант:

4. У мухи один носок и одна туфелька на каждой из её шести ножек. Сколькими различными способыми можно раздеть муху, если она не даёт снять с себя носок, если с соответствующей ноги ещё не снята туфелька?

[bot]

(Оффтоп)

Клёво. Где Вы раньше были?
А я уже задумывался над проблемой, чем муха будет одевать последний носок, если осталась неодетой одна туфелька? ...
Лишними лапками от Аристотеля?

[kknop]

Цитата:

Извиняюсь, что возвращаюсь...стало интересно. Если не ошибся, то будет верно для 56 различных натуральных чисел, не больше 1000. Через попарные разности. В массиве M(1 то 999) записываем сколько раз встречается соответствующая разность. Т.е значение $M(i)$ -сколько раз встречается разность $i$. Всего пар 1540 - это будет и сумма всех элементов массива. Если существует $k:M(k) \ge 3$ все ясно. Если все $M(k) \le 2$, то будут по крайней мере 541 двойки. И если все они сформированы только из трех элементов исходного множества, то эти элементы должны образовать арифметическую прогрессию:
$\\M(i)=2\\ a-b=b-c=i\\$

Но тогда существует индекс $k>500: M(k)=2$, а разность такой прогрессии не может быть болше 500.

Извините, что возвращаюсь, но и это явно не оптимальный результат. И метод неоптимален. Для оптимума надо брать не все попарные разности, а только несколько "близких". Для примера докажу, что все верно и при 52 не более чем трехзначных числах $a_1<a_2<...<a_{52}$. Рассмотрим разности $a_{i+k}-a_i$ при $k=1,2,3,4,5$. Всего их набралось 51+50+49+48+47=245. Если хотя бы одна разность встретилась трижды, то всё ясно. Если каждая не более двух раз, то сумма рассмотренных разностей не меньше, чем $2(1+...+122)+123=123^2=15129$. Но эта сумма равна $5a_{52}+4a_{51}+3a_{50}+2a_{49}+a_{48}-a_5-2a_4-3a_3-4a_2-5a_1$, то есть заведомо меньше, чем $15a_{52}$, откуда $a_{52}>15129/15>1000$.
Противоречие.

Это тоже, скорее всего, не лучший результат, я просто метод хотел показать... (Когда-то эту задачу Эрдёш решал, кажется, так что моей заслуги в этом методе никакой нет.)