62 Киевская городская олимпиада школьников 2007

[neo66]

Sorry.

[Capella]

11 класс

Задача 3.

Самая длиная оследовательность будет иметь $2n - 1$ длину.

Имеем один элемент, который может повторяться на каждом нечётном месте. Все остальные элементы различны. Повторный элемент может стоять как в начале, так и в конце. Общий вид:

$ a x_1 a x_2 a x_3 a ... a x_k a .... a x_{n-1} a$

Количество $x_i = n - 1, a = n$ Отсюда $2n - 1$

[neo66]

Capella писал(а):

По поводу 4 задачи за 11 класс

После обсуждения с RIPом выяснили, что в данном случае решение действительно единственное, но задачу можно модифицировать и тогда будут и другии решения.
Если кому-то интересно, то вот условие, предложенное RIPом:

$f(x^2 - y^2) = x\cdot f(x) - y \cdot f(y)$

Можно, все-таки, решение?

Добавлено спустя 54 минуты 14 секунд:

Capella писал(а):

11 класс

Задача 3.

Самая длиная оследовательность будет иметь $2n - 1$ длину.

Имеем один элемент, который может повторяться на каждом нечётном месте. Все остальные элементы различны. Повторный элемент может стоять как в начале, так и в конце. Общий вид:

$ a x_1 a x_2 a x_3 a ... a x_k a .... a x_{n-1} a$

Количество $x_i = n - 1, a = n$ Отсюда $2n - 1$

А, почему не существует более длинной последовательности?

[Lion]

Capella писал(а):

По поводу 4 задачи за 11 класс

После обсуждения с RIPом выяснили, что в данном случае решение действительно единственное, но задачу можно модифицировать и тогда будут и другии решения.
Если кому-то интересно, то вот условие, предложенное RIPом:

$f(x^2 - y^2) = x\cdot f(x) - y \cdot f(y)$

Странно, а у меня получилось только одно решение.
Ясно, что $f$ нечетна, поэтому будем рассатривать $f$ только от положительного аргумента.
Положим $y=0$, тогда $f(x^2)=xf(x)$, поэтому $f(x^2-y^2)=f(x^2)-f(y^2)$, т.е. $f$ аддитивна.
Положим $x=y+1$, тогда $2f(y)+f(1)=f(2y+1)=(y+1)f(y+1)-yf(y)=f(y)+(y+1)f(1)$, значит, $f(y)=f(1)\cdot y$.

[RIP]

Lion писал(а):

Странно, а у меня получилось только одно решение.
...
значит, $f(y)=f(1)\cdot y$.

Это не единственное решение, их целый континуум.

Добавлено спустя 24 минуты 26 секунд:

Вот мое решение (наверняка, можно попроще, но мне лень думать)
Зад.( )11-4
Кладем $x=y=0$: $f(-f(0)^2)=0\qquad(1)$.
Кладем $x=0,y=-f(0)^2$: $f(0)=-f(0)^4$, т.е. $f(0)=0,-1$.
Видно, что при любом $x\quad xf(x)=(-x)f(-x)$, поэтому при $x\ne0$ $f(-x)=-f(x)$.
Если бы было $f(0)=-1$, то имели бы (учитывая (1)) $f(1)=f(-1)=0$. Подставляя $x=y=1$ в тождество, получили бы $f(1)=-1$. Противоречие. Значит, $f(0)=0$.
Итак, $f$ нечетна, поэтому можно ее изучать на $(0;+\infty)$
Тогда из тождества при $y=0$ получаем $f(x^2)=xf(x)$, т.е.

$$f(x^2-f(y)^2)=f(x^2)-y^2$$

переписываем

$$f(x-f(y)^2)=f(x)-y^2,\quad x\ge0$$

В частности $f(f(y)^2)=y^2$, поэтому $f$ - сюрьекция.
Если $x>z\ge0$, то $z=x-f(y)^2$ для некоторого $y>0$, поэтому $f(x)=f(z)+y^2>f(z)$, т.е. $f$ строго возрастает.
Далее имеем для любых $y,z>0$
$f(zf(y)^2)=f(\{z\}f(y)^2)+\lfloor z\rfloor y^2$
Значит, существует

$$\lim_{x\to+\infty}\frac{f(x)}x=\frac{y^2}{f(y)^2}$$

Поэтому $\frac {y^2}{f(y)^2}=const$, откуда $f(x)=cx$ при некотором $c>0$. Подставляя в тождество, находим $c=1$

[Capella]

Вообще решение следует сразу из записи, а именно из $y^2$ в правой части уравнения. Если это переписать как $c \cdot y^2$, то становится очевидным, что может быть только $f^2(y) = 1^2 \cdot y^2$, а вот в примере RIPа может принимать любое значение из $c \in \mathbb{R}$

neo66 писал(а):

А, почему не существует более длинной последовательности?

Нарушит одно из условий задачи.

[Lion]

RIP писал(а):

Lion писал(а):

Странно, а у меня получилось только одно решение.
...
значит, $f(y)=f(1)\cdot y$.

Это не единственное решение, их целый континуум.

Еще не отошел после сессии.

[Macavity]

Capella писал(а):

8 класс

Задача 2

Первый толстяк - 964 страница, второй толстяк - 875 страница, третий толстяк - 123 страница. Таим образом самый толстый кусок в 752 страницы.

А почему неверно 954, 876 и 123 с разницей 753
и 945, 876 и 123 с той же разницей. Здесь, мне кажется, два решения.

[RIP]

Macavity писал(а):

А почему неверно 954, 876 и 123 с разницей 753?

А как в куске книги может быть нечетное кол-во страниц

[Macavity]

RIP писал(а):

Macavity писал(а):

А почему неверно 954, 876 и 123 с разницей 753?

А как в куске книги может быть нечетное кол-во страниц

Опа, точно. Но все равно два решения.



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

Тогда решение 954, 876, 132 с разницей 744
если нечетные, то 945, 867, 123 с разницей 744 также

[Capella]

Macavity

Хорошее замечание насчёт чётности левостороних страниц. Более логично предположить имено такую книгу (в моём варианте надо предполагать правостороний титульный лист с условным номером 0). А вот последняя разорваная часть может иметь нечётное число страниц (текст может заканчиваться на правостороней странице на чётном числе по моему варианту и перевёрнутый лист может быть пуст - не иметь числа). Думаю организаторам надо уточнять такии моменты до олимпиад
Дело в том, что первые и последнии куски могут иметь больше страниц (за счёт таких пустых страниц и происходит "выравнивание"), чем число написаное на последней странице этих кусков. А по условию спрашивается именно число.

[Macavity]

Задача 5 для 8 класса.

Из условия видно, что сумма очков, набранных игроками равна всегда 2n-1. Это значит, что ничьи не бывает, а побеждает тот игрок, который гарантированно наберет не менее n очков.
За один ход игрок может:
- подарить два очка противнику (возможно не во всех позициях);
- подарить одно очко противнику;
- подарить одно очко противнику, а одно взять себе (не во всех позициях);
- взять очко;
- взять два очка;
- ни дать и не взять ни одного очка.

Заметим, что второй игрок всегда своим ходом может принести себе как минимум одно очко. То есть каждый ход для второго игрока может быть результативным (с получением очка). Всего он должен сделать n ходов и значит за n ходов, он может взять не менее n очков (и выиграть партию). Что произойдет, если второй игрок отойдет от этой стратегии. Если первый игрок будет придерживаться этой стратегии, то он получит преимущество, то есть его n-1 ходов будут результативными (кроме первого хода) и у второго игрока тоже n-1 ходов будут результатиными (не более). Таким образом второй игрок отходя от данной статегии потеряет гарантированную победу, следовательно эта стратегия оптимальна.

В сходной задаче для 9 класса, похоже, что результат игры оптимальными стратегиями приведет к ничье.

Добавлено спустя 7 минут 37 секунд:

Capella писал(а):

Macavity

Хорошее замечание насчёт чётности левостороних страниц. Более логично предположить имено такую книгу (в моём варианте надо предполагать правостороний титульный лист с условным номером 0). А вот последняя разорваная часть может иметь нечётное число страниц (текст может заканчиваться на правостороней странице на чётном числе по моему варианту и перевёрнутый лист может быть пуст - не иметь числа). Думаю организаторам надо уточнять такии моменты до олимпиад
Дело в том, что первые и последнии куски могут иметь больше страниц (за счёт таких пустых страниц и происходит "выравнивание"), чем число написаное на последней странице этих кусков. А по условию спрашивается именно число.

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

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

[Capella]

Macavity

Вы меня неожиданно натолкнули на расширеное представление решения. Вообще говоря, там можно расписать вот так:

Имеем три группы кусков книг со сл номерами страниц: 1-123, 124-875, 876-964. Очевидно, что только синяя групп не может иметь остаточного члена (под ним можно понимать титульные листы, пустые листы в конце книги, лист с ISBN, издательством и т.д., которые не пронумерованы) из-за своей ограничености. В первой и последней формальное количество страниц не обязано совпадать с последним числом (оно может быть меньше и намного, что обычно и бывает в практике). Так что, мы вправе сказать, что число страниц обязано быть чётным только в синей группе (формально все группы будут иметь чётное оличество страниц, но не обязательно чётную разницу от номеров страниц). Отсюда максимум - абсолютный - всё-же 752 страницы.

Добавлено спустя 28 минут 17 секунд:

Macavity писал(а):

Тогда решение 954, 876, 132 с разницей 744

Если брать левосторонии страницы чётными и нуммеровать их все (начиная с титульной), то тогда лучше так 124, 876, 935 (сама книга будет иметь нечётное количество страниц). Это те-же 752

[RIP]

А я продолжу решать 7й класс. Эти задачки как раз по моим силам.
Задача 7-3.
Понятно, что составное число $n$ странное т. и т. т., к. $n$ есть степень простого, т.к. если $n$ имеет простые делители $p_1<p_2$, то в цепочке непосредственно перед $p_2$ может стоять только $d_1=1$, что явно бред.

7-4
Если $n$ - кол-во желтых столбцов, то кол-во зеленых клеток $n^2+(6-n)^2=2(n-3)^2+18$, поэтому второй игрок выиграть не может в принципе. Но он может обеспечить себе ничью, надо просто красить то же, что и первый (т.е. если первый красит строку, то и второй красит строку,...)

10-2
Докажем, что если $n\leqslant500$ странное ,то $n=2^{2k-1}$ или $n=8p$, $p>8$ - простое.
Если $n$ - степень двойки, то всё доказано.
Пусть $p$ - наим. нечетный делитель $n$. Тогда в списке делителей он имеет нумер $2l+1$ при некотором $l$. Тогда $d_j=2^{j-1}$ при $j=\overline{1,2l}$. Поскольку $d_{2l+2}\geqslant2p>2^{2l}$, то $2^{2l-1}\|n$. По условию $l\geqslant2$. Но $500\geqslant n\geqslant2^{2l-1}p>2^{4l-2}$, откуда $l<3$, т.е. $l=2$.
$n$ не могёт делиться на $p^2$ или на нечетное простое $q>p$, т.к. иначе $n>8^3>500$. Значит, $n=8p$.

[RIP]

Capella писал(а):

11 класс

Задача 3.

Самая длиная оследовательность будет иметь $2n - 1$ длину.

Имеем один элемент, который может повторяться на каждом нечётном месте. Все остальные элементы различны. Повторный элемент может стоять как в начале, так и в конце. Общий вид:

$ a x_1 a x_2 a x_3 a ... a x_k a .... a x_{n-1} a$

Количество $x_i = n - 1, a = n$ Отсюда $2n - 1$

Ответ $2n-1$ верный, но пример неверный (при $n\geqslant4$). Оценка $2n-1$ достигается на посл-ти $a_1a_2\ldots a_{n-1}a_na_{n-1}\ldots a_2a_1$.
Докво индукцией по $n$. $n=1$ - очевидно. Пусть $n>1$. Пусть $x_a=x_c$ с наибольшим возможным значением $c-a$. Пусть среди $x_1,\ldots,x_{a-1}$ $k$ разных символов, среди $x_{a+1},\ldots,x_{c-1}$ - $l$, среди $x_{c+1},\ldots,x_N$ - m.
Если символ $x_a=x_c$ больше не встречается, то $k+l+m\leqslant n-1$ (символы не могут дублироваться в разных кусках) и $N\leqslant(2k)+(2l-1)+(2m)+2\leqslant2n-1$
Иначе найдется $a<b<c$: $x_a=x_b=x_c$. Никакой символ не может повторяться $4$ раза, поэтому среди остальных символов больше нету $x_a$. Рассматривая теперь $4$ куска посл-ти, как и выше, получаем, что $N\leqslant2n-1$

Upd.
Впрочем, даже если разрешить символам повторяться больше 3 раз, то ответ $2n-1$ всё равно правильный (и пример Capellы тогда верный). Док-во то же самое с очевидными изменениями.