Городская математическая олимпиада. г. Казань, 2002 г.

[Istego]

Источник: http://weblicey.ru/filesfile/olymp/gorod/kazan_0102_9-11.pdf

10 кл.

3. На доске написано 97 чисел: 48, 24 (=48/2), 16 (=48/3), …, 48/97. За один шаг разрешается стереть с доски любые два числа a и b и записать вместо них на доску число 2ab-a-b+1. После 96 шагов на доске останется одно число. Определить множество таких чисел.

Получилось $\sum \limits _{i=1} ^n {(-1)^{i+1} 2^{i-1} p_i (x_1, …, x_n)}$ , $n = 2k + 1$, $x_i = \frac k i$, $p_i$ - элементарные симметрические многочлены. И что с этим делать? Можно ли упростить?

[RIP]

$2(2ab-a-b+1)-1=(2a-1)(2b-1)$, так что результат не зависит от последовательности стираний.

[Istego]

Совершенно верно. Приведенное мной выражение симметрично. Но оно лишком сложно для олимпиады 10 кл. Нужно что-то более прозрачное. Вероятный ответ: 0,5

[Профессор Снэйп]

Да нет, всё нормально. Для последовательности $x_1, \ldots, x_n$ инвариант $(2x_1-1)\ldots(2x_n-1)$ выглядит вполне нормально и "по школьному". Я вот гораздо хуже инвариант нашёл

$$ S(x_1, \ldots, x_n) = \sum \left\{ \prod_{i \in A} x_i \cdot \prod_{i \not\in A} (x_i-1) : A \subseteq \{ 1, \ldots, n \} \right\} $$

-- Ср ноя 04, 2009 15:57:14 --

Впрочем, это то же самое, что и у RIP, только записанное более коряво

[RIP]

Куда прозрачнее-то? Если вместо написанных чисел рассмотреть числа $96/k-1$ ($1\le k\le97$), то для них операция сводится к тому, что какие-то два числа заменяются произведением. Среди (новых) чисел есть 0, поэтому 0 в конце и останется, т.е. для начальной последовательность получится $0.5$. Как ни крути.

[Istego]

Мои рассуждения: ищем 0 преобразования. $2ab-a-b+1=a; a=\frac 1 2; \frac 1 2 = \frac {48} i; i = 96$ Нашли ноль, принадлежащий исходному множеству.

-- Ср ноя 04, 2009 13:18:41 --

По адресу: http://otvet.mail.ru/question/31475671/ находится вариант задачи с несимметричной функцией преобразования.

На доске записаны 67 чисел: 12, 6, 4,...12/67 (эти числа определяются формулой 12/n, где знаменатель принимает значения от 1 до 67). За один шаг разрешается стереть с доски любые два числа a и b и записать вместо них на доску число 3ab - a - 2b + 1. После 66 шагов на доске останется одно число. Каким оно может быть?

Имеем правый ноль: $\frac 1 3$ ($\frac {12} {36}$)

[Профессор Снэйп]

Istego в сообщении #258201 писал(а):

Мои рассуждения: ищем 0 преобразования. $2ab-a-b+1=a; a=\frac 1 2; \frac 1 2 = \frac {48} i; i = 96$ Нашли ноль, принадлежащий исходному множеству.

Что-то я ничего тут не понимаю.

У Вас в левой части равенства $2ab-a-b+1=a$ две переменных, в правой одна. Какой такой ноль имеется в виду? Я не понимаю саму идею этих выкладок.

[Istego]

Ничего страшного. Я сам иногда не понимаю
$f(a,b)=2ab-a-b+1; a f(a,b) b = a;$ По аналогии с $0 * a = 0$

[Профессор Снэйп]

Istego в сообщении #258317 писал(а):

Ничего страшного. Я сам иногда не понимаю
$f(a,b)=2ab-a-b+1; a f(a,b) b = a;$ По аналогии с $0 * a = 0$

Опять не понял: $a f(a,b) b = 2a^2b^2 - a^2b - ab^2 + ab \neq a$.

[Istego]

Профессор Снэйп

$a$, удовлетворяющее $f(a,b)=f(b,a)=a$, можно назвать "нулем" бинарной операции $f$. Нужно ли определять множество, на котором определена эта операция? И чем является множество с этой операцией?

Меня больше интересует вторая задача.

[Профессор Снэйп]

Istego в сообщении #258332 писал(а):

[b]$a$, удовлетворяющее $f(a,b)=f(b,a)=a$, можно назвать "нулем" бинарной операции $f$.

А почему не единицей? Ваша терминология воистину понятна только Вам самому! Я бы порекомендовал в следующий раз пользоваться термином "нейтральный элемент".

Istego в сообщении #258332 писал(а):

Меня больше интересует вторая задача.

Какая ещё "вторая задача"? Вроде в теме фигурирует только одна задача (номер три из списка задач олимпиады).

[Istego]

На доске записаны 67 чисел: 12, 6, 4,...12/67 (эти числа определяются формулой 12/n, где знаменатель принимает значения от 1 до 67). За один шаг разрешается стереть с доски любые два числа a и b и записать вместо них на доску число 3ab - a - 2b + 1. После 66 шагов на доске останется одно число. Каким оно может быть?

Имеем "правый нейтральный элемент" : $\frac 1 3$ и "левый нэ": $1$

-- Ср ноя 04, 2009 19:43:55 --

Да, "нейтральным элементом" или "единицей" я бы назвал $a$, отвечающее $f(a, b)=b$. Но как Вам будет угодно.

[Профессор Снэйп]

Я не понимаю, зачем нужны эти нейтральные элементы и что они дают.

[Istego]

Не знаю В первом случае "он" помог мне решить задачу.

[Профессор Снэйп]

Istego в сообщении #258336 писал(а):

Да, "нейтральным элементом" или "единицей" я бы назвал $a$, отвечающее $f(a, b)=b$. Но как Вам будет угодно.

Наверное, так лучше. Запутался в Ваших соображениях, определениях, обозначениях. А всё потому, что не понимаю идею.

Istego в сообщении #258341 писал(а):

В первом случае "он" помог мне решить задачу.

Я верю, что помог, но не понимаю как.