Олимпиада НГУ по математике 28.09.08

[TOTAL]

В.П. писал(а):

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

Все задачи тривиальны.

Не согласен, 2 и 5 вполне приличные олимпиадные задачи, только формулировки следует уточнить. Даже не смотря на то, что знаю код Грея, не сразу увидел решение 5-й задачи. Причём, ещё 6=2x3 нужно отдельно рассматривать.

Среди 16 четырёхзначных двоичных чисел есть либо нулевое, либо два одинаковых. - как здесь 6=2x3 является отдельным случаем?

Код Грея - это что? (Не о том ли речь, чтобы предъявить цепочку из 15 ненулевых четырехзначных двоичных чисел с отличием соседних чисел в одном разряде?)

[Руст]

В чём не тривиальность 2-ой задачи. Пусть $f(x_1,y_1)$ махимум или если оно недостижимо находится в епсилон окрестности максимума (для бесконечности ерсилон окрестность можно определить через 1/z) и $f(x_2,y_2)$ аналогичный минимум. Тогда фиксируем второй аргумент взяв некоторое рациональное значение бесконечно близкое k $y_1$ и движемся по первой координате до значения бесконечно близкого к $x_2$, потом аналогично по второй координате. Т.е. образ линейно связен. Все линейно связные в R множества это интервалы с открытыми или закрытыми концами типа $(a,b),[a,b),(a,b],[a,b]$, когда один из чисел бесконечен то этот конец открытый.

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

В.П. писал(а):

Произвольный промежуток. Я полагаю. То есть как Вы сами написали - линейно связное множество.

Упс!.. Ну я слепой тупица!!!

Почему-то все эти несколько дней, пока задача тут висела, я размышлял над ней, считая, что $f$ --- непрерывное отображение из $\mathbb{R}^2$ в $\mathbb{R}^2$, а не из $\mathbb{R}^2$ в $\mathbb{R}$. А это, согласитесь, гораздо более сложная задача! Я так и не нашёл к ней нормального ответа, из-за чего моя самооценка упала ниже некуда. А надо было всего лишь протереть глаза и внимательно прочитать условие.

[xaxa3217]

интересует последняя задача для произвольного основания системы счисления. решаю так:
натуральное число является квадратом некоторого целого числа <=> степени при различных простых делителях четные. одновременно с этим, убеждаемся, что нам важна только четность (0 или 1) при соответствующих простых числах меньших основания - 2 3 5 7. рассмотрим n записей соответствующих цифр n-значного числа интересуясь только четностью при простых делителях:
2 3 5 7

1 1 0 0 - число 6 (2*3)
1 0 0 0 - либо 2, либо 8
и тд

обозначим i-ую запись за z(i), тогда произведение с i-ой по j-ую цифру является квадратом целого числа когда z(i)^..^z(j) = 0 0 0 0, где ^ - сложение по модулю 2 значений в соотв. столбцах. пусть s(i) = z(0)^..^z(i), тогда можно говорить, что искомая подстрока цифр найдется, когда найдутся i и j: s(i)=s(j), i != j. предполагая, от противного, что s(i) не принимает значения 0 0 0 0 и различных значений не более 2^4 -1 это, по принципу дирихле, выполняется при n=2^4.
аналогично и для других оснований. но вот как быть с доказательством того, что для n < 2^m это уже не работает? имеется ввиду как обойти построение контрпримера и доказать это нормально?
--
сложность у меня тут вот в чем: при n < 2^m можно выбрать попарно различные и не равные нулю s(i), но вполне возможно, что обратное восстановление по ним z(i) = s(i)^s(i-1) не будет цифрой, то есть z(i) может оказаться равным, например, 0 1 1 0 соответствующего как минимум числу 15 > 9 =m-1

[bot]

xaxa3217 в сообщении #147514 писал(а):

но вот как быть с доказательством того, что для n < 2^m это уже не работает? имеется ввиду как обойти построение контрпримера и доказать это нормально?

А зачем обходить построение контрпримера, если его построение очевидно?
Из $(2^{m-1}-1)$-значного, в котором были только m-1 простых строим $(2^{m}-1)$-значный окаймлением с двух сторон m-го простого $(2^{m-1}-1)$-значными.

Посмотрите, что

Руст в сообщении #147251 писал(а):

Достаточно использовать только простые цифры. Например 757375727573757

В точности так он и построил.

[xaxa3217]

ух ты, мне, к сожалению, не было очевидно построение контрпримера от Руст'а а оно оказывается в общем случае так же просто работает.. спасибо!

[В.П.]

TOTAL писал(а):

Среди 16 четырёхзначных двоичных чисел есть либо нулевое, либо два одинаковых. - как здесь 6=2x3 является отдельным случаем?

В условии задачи не сказано, что цифры только простые. Понятно, что 0,1,4,9 можно вообще не рассматривать, а 8 заменить на 2. Но отсутствие 6 в минимальном контрпримере нужно отдельно обосновать.

TOTAL писал(а):

Код Грея - это что? (Не о том ли речь, чтобы предъявить цепочку из 15 ненулевых четырехзначных двоичных чисел с отличием соседних чисел в одном разряде?)

Да. Требуемая последовательность цифр - это номера изменяющихся разрядов в коде Грея.

[TOTAL]

В.П. писал(а):

В условии задачи не сказано, что цифры только простые. Понятно, что 0,1,4,9 можно вообще не рассматривать, а 8 заменить на 2. Но отсутствие 6 в минимальном контрпримере нужно отдельно обосновать.

Не понял, что и зачем надо дополнительно обосновывать? В каком минимальном контрпримере?
Если имеете в виду пример из $15$ цифр, то вот с шестёркой, она не отсутствует: $637573756573757$

[В.П.]

TOTAL писал(а):

В.П. писал(а):

В условии задачи не сказано, что цифры только простые. Понятно, что 0,1,4,9 можно вообще не рассматривать, а 8 заменить на 2. Но отсутствие 6 в минимальном контрпримере нужно отдельно обосновать.

Не понял, что и зачем надо дополнительно обосновывать? В каком минимальном контрпримере?

Почему не существует числа из 16 цифр, в котором подряд идущие цифры не дают в произведении квадратов, когда среди этих цифр присутствуют 6? Если различных цифр только 4, то это ясно.

[TOTAL]

В.П. писал(а):

Почему не существует числа из 16 цифр, в котором подряд идущие цифры не дают в произведении квадратов, когда среди этих цифр присутствуют 6? Если различных цифр только 4, то это ясно.

Вот число из 16 произвольных цифр $ABCD EFGH IJKL MNOP$.
Среди произведений $A, \; AB, \; ABC, \;$ и т.д. либо встретится нулевое, либо встретятся одинаковые, ну что ещё надо, где здесь особые случаи? Под произведением понимается четырехзначное двоичное число, в котором первый разряд равен единице, если двойка входит в нечетной степени и т.д.

[В.П.]

TOTAL писал(а):

...Под произведением понимается четырехзначное двоичное число, в котором первый разряд равен единице, если двойка входит в нечетной степени и т.д.

Только сейчас прочитал доказательство xaxa3217 и всё понял.

[bot]

26. 10. 2008

МЕЖВУЗОВСКАЯ ОЛИМПИАДА ПО МАТЕМАТИКЕ 2008 г. (НГУ)
ДЛЯ ВУЗОВ МАТЕМАТИЧЕСКОГО ПРОФИЛЯ.

1. У Винни-Пуха было 9 запечатанных горшочков с мёдом. На каждом был написана масса горшочка вместе с мёдом в килограммах: $1, 2, 3,\ \dots,\ 9$. На день рождения ему принесли килограмм орехов. Винни-Пух распечатал один из горшочков, засыпал туда орехи, снова запечатал, а отметить этот горшочек забыл.
а) Не распечатывая горшочков помогите Винни-Пуху найти горшочек с орехами за два взвешивания на равноплечих весах без гирь.
б) Винни-Пух съел мёд из пяти горшочков, в них орехов не оказалось. Всегда ли теперь будет достаточно двух взвешиваний, чтобы справиться с той же проблемой?

2. Доказать, что уравнение $x^{2008}+A\cos (2\pi x + \varphi )= \frac{1}{2009}$ имеет корень на промежутке $(0;\ 1)$ при любых $A,\ \varphi \in \mathbb R $.

3. Найти $\inf\limits_{x\in \mathbb R}\frac{\sin 2nx }{\sin x}$ и $\sup\limits_{x\in \mathbb R}\frac{\sin 2nx }{\sin x}.$

4. Найти все трёхчлены вида $x^n+x+a$ с нечётным $a$, которые делятся без остатка на $x^2-x+b$ при некотором целом $b.$

5. Верно ли, что любые четыре попарно скрещивающихся прямые можно так пересечь некоторой плоскостью, что точки её пересечения с этими прямыми будут вершинами параллелограмма?

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

В первой задаче я условие не до конца понял. Он перед тем, как сыпать орехи, мёд из горшочка куда-то слил (слопал) или он прям в мёд эти орехи насыпал?

[Руст]

в a) мёд остался. Иначе, не зная, что горшочек с орехами тяжелее (можно конечно и легче) чем остальные, т.е. в какую сторону отклоняются весы с орехами задачу с 9 горшками не решить. Сама задача о фальшивой монете, как при информации тяжелее, легче, так и без оной, здесь многократно обсуждалось.

[xaxa3217]

можно переформулировать так: есть 9 горшков на которых написан их номер, ровно 8 горшков имеют вес соответствующий номеру, и один вес равный номеру плюс 1, за два взвешивания определить горшок вес которого не соотв. своему номеру.
ну решение тут очевидное - перво-наперво разобъем на три группы с предположительно равными весами ($\frac{45}{3}=15$)по три горшка, например: $195, 276, 348$ взвешиваем любые два, если вес одинаковый то горшок с сюрпризом в третьей, иначе в той которая перевешивает (раз весы такие удобные), итак у нас одна кучка из трех горшков один из которых с орехам. берем из этой кучки один горшок на левую сторону весов второй на правую, и из тех групп горшков что точно без орехов ставим горшки на левую и правую сторону так чтобы предполагаемый (то есть сумма номеров была равна или даже отличалась, но не более чем на единицу, а это всегда сделать можно - проверяется хотя бы перебором вариантов:)) вес был одинаковый, ну и определяем искомый горшок. по второму пункту - пусть остались горшки - $1, 2, 5, 9$ и пускай орехи лежат например в 1 -ом горшке, тогда первое необходимое взвешивание - 1,2,5 и 9 (тк все остальные распределения по весам делают разность сумм номеров большей 1, откуда нельзя определить сторону с искомым горшком), далее остается три горшка 1,2,5, но тут почти аналогичная ситуация - нам нужно взвесить ровно два горшка из этой кучки на разных сторонах весов, но в любом случае разница сумм номеров будет больше единицы (тк остальные горшки без меда и стало быть не могут ничем помочь).