Решить по-русски

Ian · Сообщение **Ian** » 23 окт 2011, 16:14

Здесь мы будем публиковать переводы задачек, которые в первоисточнике не получили (пока?) удовлетворительного решения. Преимущество перед первоисточником, что решение можно написать по-русски.

1..Энни и Дженни играют в угадывание чисел. Энни скрытно записывает одно из чисел множества Х=(1,2,...144). Дженни может выбрать любое подмножество А в Х и спросить Энни "верно ли, что записанное число принадлежит А?" За ответ "да" Дженни платит 2 доллара, а за ответ "нет" 1 доллар. Как много долларов необходимо Дженни, чтобы точно узнать записанное число?

СергейП

Ian писал(а):Source of the post
Здесь мы будем публиковать переводы задачек, которые в первоисточнике не получили (пока?) удовлетворительного решения. Преимущество перед первоисточником, что решение можно написать по-русски.

1..Энни и Дженни играют в угадывание чисел. Энни скрытно записывает одно из чисел множества Х=(1,2,...144). Дженни может выбрать любое подмножество А в Х и спросить Энни "верно ли, что записанное число принадлежит А?" За ответ "да" Дженни платит 2 доллара, а за ответ "нет" 1 доллар. Как много долларов необходимо Дженни, чтобы точно узнать записанное число?

Интересный выход на числа Фиббоначи!

bot · Сообщение **bot** » 23 окт 2011, 17:10

144. Называю любые 55 чисел и имею их за 2 бакса либо оставшиеся 89 за 1
89. Называю любые 34 ...
55. Называю лю...
34. Назы...
21. ...
...

11 12 всё-таки 11 баксов хватит.

Упс, пока колебался-выверялся, да осторожничал - обошли.

Ian · Сообщение **Ian** » 23 окт 2011, 17:27

Таким образом, число долларов= номер ближайшего не меньшего числа Фибоначчи
Пример:
1й вопрос про 55,ответ Да, стоит 2
2й вопрос про 21,ответ Да , стоит 2
3й вопрос про 8, ответ Нет, стоит 1
4й вопрос про 5. ответ Да , стоит 2
5й вопрос про 2, ответ Да, стоит 2
6й вопрос про 1, худший ответ Да, т.к. стоит 2
На каждом этапе количество элементов множества А=числу Фибоначчи.

Продолжим...
2. Дженни выложила 365 карточек с числами 1,..365 в ряд числами вниз. Энни может указать 3 карточки, чтобы Дженни поменяла их местами в порядке возрастания слева направо, но самих чисел Энни при этом не увидит. За одну указанную тройку карточек Энни платит 1 доллар. Потом Энни может выбрать любые 3 карточки из 365,и т.д. Сколько долларов ей надо иметь, чтобы с гарантией добиться, что все 365 чисел стоят в порядке возрастания?
Мое примечание: как именно происходила перестановка, Энни видит и может это использовать, хотя и не видит числа на карточках.
IT-шная задачка, одна из стран перед IMO-2011 тренировалась на ней

VAL · Сообщение **VAL** » 23 окт 2011, 17:27

bot писал(а):Source of the post
Упс, пока колебался-выверялся, да осторожничал - обошли.

Я тоже решил в кои-то веки что-то решить, а не только других мучить. Когда увидел задачу, ответов еще не было. И решил, как мне казалось, довольно быстро... Но не тут-то было
Недаром не люблю я эти ваши золотые сечения

Ian · Сообщение **Ian** » 25 окт 2011, 00:59

Ian писал(а):Source of the post 2. Дженни выложила 365 карточек с числами 1,..365 в ряд числами вниз. Энни может указать 3 карточки, чтобы Дженни поменяла их местами в порядке возрастания слева направо, но самих чисел Энни при этом не увидит. За одну указанную тройку карточек Энни платит 1 доллар. Потом Энни может выбрать любые 3 карточки из 365,и т.д. Сколько долларов ей надо иметь, чтобы с гарантией добиться, что все 365 чисел стоят в порядке возрастания?

У меня вышло 1825, рекурсия в которой не нужен комп, хотя по ходу дела использовал.
Обозначим $$A_n$$

решение задачи(по используемому здесь алгоритму) для n карточек, $$A_3=1$$

, и

-число ходов, за которые можно точно определить место среди упорядоченных $$n-1$$

карточек карточки, про которую ничего не было известно. $$a_2=a_3=1$$

. Выводим
$a_n=1+a_{\lfloor\frac n3\rfloor}$ (округление вверх)
Например, $$n=10$$

и уже упорядочены k1<k2<...<k9. Задаем упорядочить новую k с k3 и k7, в худшем случае k3<k<k7 останется упорядочить k с еще тремя k4,k5,k6 за 2 доллараПо индукции получаем $a_n=\lfloor\log_3n\rfloor$ ,
а $A_n=A_3+a_4+...+a_n\sim\log_3(n!)\sim n\log_3n$
Доказательства, что алгоритм оптимален, правда, нет.

Полно там задачек, кто решит заказывайте, на какую тему еще перевести
Пока комбинаторная геометрия
3.. На плоскости расположены n точек, расстояние между любыми двумя из которых не более 1. Доказать, что найдутся две точки на расстоянии, не большем $\frac{\sqrt 2}{\sqrt n-1}$
Продолжение(напрашивается) Найти наименьшее С, что при некотором $$a$$

для каждого $$n>a^2$$

минимальное расстояние не больше $\frac C{\sqrt n-a}$
Они have nothing to say, а у нас была 2 года назад похожая задачка (но не эта)

IRINA · Сообщение **IRINA** » 25 окт 2011, 04:17

Ian писал(а):Source of the post Как много долларов

Раз уж по-русски, то нужно ещё перевести в рубли согласно курса.

Ian · Сообщение **Ian** » 27 окт 2011, 12:32

Ian писал(а):Source of the post 3.. На плоскости расположены n точек, расстояние между любыми двумя из которых не более 1. Доказать, что найдутся две точки на расстоянии, не большем $\frac{\sqrt 2}{\sqrt n-1}$
Продолжение(напрашивается) Найти наименьшее С, что при некотором для каждого минимальное расстояние не больше $\frac C{\sqrt n-a}$
Они have nothing to say, а у нас была 2 года назад похожая задачка (но не эта)

Но эти специалисты заняты, грят, поэтому сам. Рассмотрим сетку триангуляции со стороной х, такую, что ровно n-1 треугольников пересекаются с выпуклой оболочкой этих n точек, а значит все они лежат в х- окрестности этой выпуклой оболочки , диаметр ее 1+2х, по изопериметрическому и др. неравенствам площадь этой окрестности не более $\frac{\pi}4(1+2x)^2$ , а треугольники суммарной площадью $(n-1)\frac{x^2\sqrt 3}4$ целиком лежат в ней . Решаем неравенство относительно х, получаем
$\displaystyle x\leqslant\frac{\sqrt[4]{3}}{\sqrt{\pi}}\cdot\frac 1{\sqrt{n-1-\frac{2\pi}{\sqrt 3}}}$
а так как по Дирихле 2 из n точек окажутся в одном треугольнике, то расстояние между ними еще меньше.
Оценка $\displaystyle C=\frac{\sqrt[4]{3}}{\sqrt{\pi}}=1,34$ является точной, достаточно рассмотреть пересечение достаточно мелкой сетки триангуляции с кругом диаметра 1. В сайте-первоисточнике С=2, а для док-ва заданного $C=\sqrt 2$ надо было заключить n точек в единичный квадрат и разбить на не более чем (n-1) квадратиков.

Вот другая комбинаторная геометрия, интересно не было ли в книгах:
4. а)Дано конечное множество квадратиков общей площадью 3. Доказать, что им можно покрыть единичный квадрат.
б)Дано конечное множество квадратиков общей площадью $\frac 12$ . Доказать, что их можно разместить без пересечений в единичном квадрате.

Ian · Сообщение **Ian** » 29 окт 2011, 16:01

Согласен, 4-я задача трудная. как и все у того ТСа. В первоисточнике продвижений нет, и мы отложим.

А вот по этой у них непонятки пошли.
5. Пусть $$1<a_1<a_2<...$$

бесконечная последовательность натуральных чисел. Доказать, что $\displaystyle \sum_{n=1}^{\infty}\frac{2^{a_n}}{a_n!}$ является иррациональным числом.
Кто помнит док-во иррациональности е через ряд, думаю решит

UPD: Там решили, пост6, для просмотра надо щелкнуть по номеру задачи. Но у меня намного проще.
Пусть $\sum_{n=1}^{\infty}\frac{2^{a_n}}{a_n!}=\frac pq$ Неравенство
$0<|\frac pq-\sum_{k=1}^{n}\frac{2^{a_k}}{a_k!}|\leqslant\frac{2}{a_n!(a_n-1)}$ доказывается аналогично оценке остаточного члена ряда для экспоненты. Напишем это неравенство для $$a_n>q+1$$

и умножим на $$a_n!$$

, тогда под модулем целое число $0<|\frac{pa_n!}{q}-\sum_{k=1}^{\infty}\frac{2^{a_k}a_n!}{a_k!}|\leqslant\frac 1{a_n-1}<1$ противоречие.
Пишите отзывы, кто решал, и какие задачи переводить

Ian · Сообщение **Ian** » 01 ноя 2011, 21:16

По задаче 4 еще поговорим.
Текущая новость:
6.Вычислить $\displaystyle \int_0^1\{\frac 1x\}dx$ , где фиг.скобки обозначают дробную часть числа.
Там есть пост, но недостигший нужного результата

yourdomain.com