2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение30.09.2008, 10:15 
Заслуженный участник
Аватара пользователя


23/08/07
5500
Нов-ск
В.П. писал(а):
Руст писал(а):
Все задачи тривиальны.

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

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

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

 Профиль  
                  
 
 
Сообщение30.09.2008, 11:23 
Заслуженный участник


09/02/06
4401
Москва
В чём не тривиальность 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]$, когда один из чисел бесконечен то этот конец открытый.

 Профиль  
                  
 
 
Сообщение30.09.2008, 11:38 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
В.П. писал(а):
Произвольный промежуток. Я полагаю. То есть как Вы сами написали - линейно связное множество.


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

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

 Профиль  
                  
 
 
Сообщение30.09.2008, 12:22 
Аватара пользователя


30/09/08
99
москва
интересует последняя задача для произвольного основания системы счисления. решаю так:
натуральное число является квадратом некоторого целого числа <=> степени при различных простых делителях четные. одновременно с этим, убеждаемся, что нам важна только четность (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

 Профиль  
                  
 
 
Сообщение30.09.2008, 12:40 
Заслуженный участник
Аватара пользователя


21/12/05
5932
Новосибирск
xaxa3217 в сообщении #147514 писал(а):
но вот как быть с доказательством того, что для n < 2^m это уже не работает? имеется ввиду как обойти построение контрпримера и доказать это нормально?
А зачем обходить построение контрпримера, если его построение очевидно?
Из $(2^{m-1}-1)$-значного, в котором были только m-1 простых строим $(2^{m}-1)$-значный окаймлением с двух сторон m-го простого $(2^{m-1}-1)$-значными.

Посмотрите, что
Руст в сообщении #147251 писал(а):
Достаточно использовать только простые цифры. Например 757375727573757


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

 Профиль  
                  
 
 
Сообщение30.09.2008, 12:50 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение30.09.2008, 14:34 


29/04/08
20
Новосибирск
TOTAL писал(а):
Среди 16 четырёхзначных двоичных чисел есть либо нулевое, либо два одинаковых. - как здесь 6=2x3 является отдельным случаем?

В условии задачи не сказано, что цифры только простые. Понятно, что 0,1,4,9 можно вообще не рассматривать, а 8 заменить на 2. Но отсутствие 6 в минимальном контрпримере нужно отдельно обосновать.
TOTAL писал(а):
Код Грея - это что? (Не о том ли речь, чтобы предъявить цепочку из 15 ненулевых четырехзначных двоичных чисел с отличием соседних чисел в одном разряде?)

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

 Профиль  
                  
 
 
Сообщение30.09.2008, 14:51 
Заслуженный участник
Аватара пользователя


23/08/07
5500
Нов-ск
В.П. писал(а):
В условии задачи не сказано, что цифры только простые. Понятно, что 0,1,4,9 можно вообще не рассматривать, а 8 заменить на 2. Но отсутствие 6 в минимальном контрпримере нужно отдельно обосновать.
Не понял, что и зачем надо дополнительно обосновывать? В каком минимальном контрпримере?
Если имеете в виду пример из $15$ цифр, то вот с шестёркой, она не отсутствует: $637573756573757$

 Профиль  
                  
 
 
Сообщение30.09.2008, 16:05 


29/04/08
20
Новосибирск
TOTAL писал(а):
В.П. писал(а):
В условии задачи не сказано, что цифры только простые. Понятно, что 0,1,4,9 можно вообще не рассматривать, а 8 заменить на 2. Но отсутствие 6 в минимальном контрпримере нужно отдельно обосновать.
Не понял, что и зачем надо дополнительно обосновывать? В каком минимальном контрпримере?

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

 Профиль  
                  
 
 
Сообщение30.09.2008, 16:17 
Заслуженный участник
Аватара пользователя


23/08/07
5500
Нов-ск
В.П. писал(а):
Почему не существует числа из 16 цифр, в котором подряд идущие цифры не дают в произведении квадратов, когда среди этих цифр присутствуют 6? Если различных цифр только 4, то это ясно.

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

 Профиль  
                  
 
 
Сообщение01.10.2008, 07:49 


29/04/08
20
Новосибирск
TOTAL писал(а):
...Под произведением понимается четырехзначное двоичное число, в котором первый разряд равен единице, если двойка входит в нечетной степени и т.д.

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

 Профиль  
                  
 
 
Сообщение26.10.2008, 11:59 
Заслуженный участник
Аватара пользователя


21/12/05
5932
Новосибирск
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. Верно ли, что любые четыре попарно скрещивающихся прямые можно так пересечь некоторой плоскостью, что точки её пересечения с этими прямыми будут вершинами параллелограмма?

 Профиль  
                  
 
 
Сообщение27.10.2008, 13:18 
Заморожен
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение27.10.2008, 13:49 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение27.10.2008, 14:02 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group