yourdomain.com

Краткое описание форума
http://e-science11.ru/test_forum/

Интересные олимпиадные задачи

http://e-science11.ru/test_forum/viewtopic.php?f=9&t=70269

Страница 5 из 8

Интересные олимпиадные задачи

Добавлено: 07 июн 2007, 18:05
bot
andrej163 писал(а):Source of the post
...

Угу - то есть каждый сообщает впереди стоящему сумму цветов по модулю k. Получается треугольная система линейных уравнений.
Оно и есть.

Интересные олимпиадные задачи

Добавлено: 07 июн 2007, 21:37
Natrix
a_l_e_x86 писал(а):Source of the post
andrej163 писал(а):Source of the post
Конечно выгодно!!!!
Если ведущий знает, в какой шкатулке что находится, то он открывает ту из оставшихся шкатулок, в которой ничего нет, и всегда предлагает игроку изменить свой выбор, то вероятность того, что приз находится в выбранной игроком шкатулке, равна 1/3, и, соответственно, вероятность того, что деньги находятся в оставшейся шкатулке, равна 2/3. Таким образом, изменение первоначального выбора увеличивает шансы игрока в 2 раза.
Хотя на первый взгляд кажется, что никакой разницы нет, что открывать уже выбраннуюю шкатулку, что открывать оставшеюся!!!!!
Парадокс Монти Холла!!!!!

хм.. a почему 2/3 можно поподробней

Построим дерево.
Игрок выбрал ДЕНЬГИ.
Вероятность 1/3. Якубович открыл ПУСТО1 (ПУСТО2).
He менял - ВЫИГРАЛ. Поменял - ПРОИГРАЛ
Игрок выбрал ПУСТО1.
Вероятность 1/3
Якубович открыл ПУСТО2.
He менял - ПРОИГРАЛ. Поменял - ВЫИГРАЛ
Игрок выбрал ПУСТО2.
Вероятность 1/3
Якубович открыл ПУСТО1.
He менял - ПРОИГРАЛ. Поменял - ВЫИГРАЛ

Интересные олимпиадные задачи

Добавлено: 07 июн 2007, 21:41
andrej163
Natrix писал(а):Source of the post
Построим дерево.
Игрок выбрал ДЕНЬГИ.
Вероятность 1/3. Якубович открыл ПУСТО1 (ПУСТО2).
He менял - ВЫИГРАЛ. Поменял - ПРОИГРАЛ
Игрок выбрал ПУСТО1.
Вероятность 1/3
Якубович открыл ПУСТО2.
He менял - ПРОИГРАЛ. Поменял - ВЫИГРАЛ
Игрок выбрал ПУСТО2.
Вероятность 1/3
Якубович открыл ПУСТО1.
He менял - ПРОИГРАЛ. Поменял - ВЫИГРАЛ

Интересное доказательство!!!!

Интересные олимпиадные задачи

Добавлено: 07 июн 2007, 21:56
a_l_e_x86
Можно все гораздо проще объяснить. Поскольку вероятность того, что обе шкатулки будут пустые в 2 раза меньше того, что одна из них будет в деньгами то выгодно менять

Интересные олимпиадные задачи

Добавлено: 07 июн 2007, 21:57
andrej163
a_l_e_x86 писал(а):Source of the post
Можно все гораздо проще объяснить. Поскольку вероятность того, что обе шкатулки будут пустые в 2 раза меньше того, что одна из них будет в деньгами то выгодно менять

Это да, просто у Миши мне понравился подход!!!!

Интересные олимпиадные задачи

Добавлено: 08 июн 2007, 01:08
Pavlukhin
я что то так и не врубился в решение андрея про шапки, но свое для двух шапок придумал такое
последний говорит скажем синий если число синих шапок впереди него четно и красный если нечетно, тепеь каждый может посчитав количество синих шапок сказать какая шапка на нем...

Интересные олимпиадные задачи

Добавлено: 08 июн 2007, 14:56
bot
Pavlukhin писал(а):Source of the post
я что то так и не врубился в решение андрея про шапки, но свое для двух шапок придумал такое
последний говорит скажем синий если число синих шапок впереди него четно и красный если нечетно, тепеь каждый может посчитав количество синих шапок сказать какая шапка на нем...

Оно и есть.
Это означает
Синий=1,
Красный=0
сложение (или вычитание - здесь безразлично) по модулю два. Можно переключатель устроить: палец согнут или разогнут.

Для k цветов то же самое (только одним пальцем уже не обойтись):
Bce цвета занумеруем числами $$0, 1, ... , k-1$$, a n умников в порядке их очерёдности занумеруем от 0 до n-1.
Цвет шапки на i-м узнике пусть будет $$x_i$$
Начинает отвечать умник c номером 0. Его главная задача не угадать свой цвет, a передать впереди стоящим такую информацию, чтобы каждый c учётом всех услышанных ответов сзади стоящих умников, мог вычислить сой цвет. Вот эта информация:

$$S_1=x_1 + x_2 + ... + x_{n-1} \pmod{k}$$

B самом деле, 1-й узник видит перед собой $$S_2=x_2 + ... + x_{n-1} \pmod{k}$$, поэтому услышав $$S_1 \pmod{k}$$, вычисляет $$x_1=S_1-S_2 \pmod{k}$$, остальные узники услышав $$x_1$$ вычисляют $$S_2 \pmod{k}$$, очередной (то есть второй) вычисляет свой цвет и, называя его, передаёт эту информацию наверх ...

Интересные олимпиадные задачи

Добавлено: 08 июн 2007, 16:18
Pavlukhin
bot писал(а):Source of the post
Pavlukhin писал(а):Source of the post
я что то так и не врубился в решение андрея про шапки, но свое для двух шапок придумал такое
последний говорит скажем синий если число синих шапок впереди него четно и красный если нечетно, тепеь каждый может посчитав количество синих шапок сказать какая шапка на нем...

Оно и есть.
Это означает
Синий=1,
Красный=0
сложение (или вычитание - здесь безразлично) по модулю два. Можно переключатель устроить: палец согнут или разогнут.

Для k цветов то же самое (только одним пальцем уже не обойтись):
Bce цвета занумеруем числами $$0, 1, ... , k-1$$, a n умников в порядке их очерёдности занумеруем от 0 до n-1.
Цвет шапки на i-м узнике пусть будет $$x_i$$
Начинает отвечать умник c номером 0. Его главная задача не угадать свой цвет, a передать впереди стоящим такую информацию, чтобы каждый c учётом всех услышанных ответов сзади стоящих умников, мог вычислить сой цвет. Вот эта информация:

$$S_1=x_1 + x_2 + ... + x_{n-1} \pmod{k}$$

B самом деле, 1-й узник видит перед собой $$S_2=x_2 + ... + x_{n-1} \pmod{k}$$, поэтому услышав $$S_1 \pmod{k}$$, вычисляет $$x_1=S_1-S_2 \pmod{k}$$, остальные узники услышав $$x_1$$ вычисляют $$S_2 \pmod{k}$$, очередной (то есть второй) вычисляет свой цвет и, называя его, передаёт эту информацию наверх ...

Оно и есть. По сути это означает
Синий=1,
Красный=0
сложение (или вычитание - здесь безразлично) по модулю два, можно смоделировать изменением или сохранением положения согнутого/разогнутого пальца в зависимости от очередного услышанного ответа сзади стоящего.

Для k цветов то же самое (только одним пальцем уже не обойтись):
Bce цвета занумеруем числами $$0, 1, ... , k-1$$, a n умников в порядке их очерёдности занумеруем от 0 до n-1.
Цвет шапки на i-м узнике пусть будет $$x_i$$
Начинает отвечать умник c номером 0. Его главная задача не угадать свой цвет, a передать впереди стоящим такую информацию, чтобы каждый c учётом всех услышанных ответов сзади стоящих умников, мог вычислить сой цвет. Вот эта информация:

$$S_1=x_1 + x_2 + ... + x_{n-1} \pmod{k}$$

B самом деле, 1-й узник видит перед собой $$S_2=x_2 + ... + x_{n-1} \pmod{k}$$, поэтому услышав $$S_1 \pmod{k}$$, вычисляет $$x_1=S_1-S_2 \pmod{k}$$, остальные узники услышав $$x_1$$ вычисляют $$S_2 \pmod{k}$$, очередной (то есть второй) вычисляет свой цвет и, называя его, передаёт эту информацию наверх ...


хахахх..это чтоли аткой финт чтобы обьяснение дошло??
написать два раза? :acute:

Интересные олимпиадные задачи

Добавлено: 08 июн 2007, 16:30
bot
Pavlukhin писал(а):Source of the post
хахахх..это чтоли аткой финт чтобы обьяснение дошло??
написать два раза? :acute:


Один раз уже исправлял - стало быть было трижды!!! :lool:
Исправил ещё раз.

Интересные олимпиадные задачи

Добавлено: 16 июн 2007, 11:42
a_l_e_x86
Предлагаю еще несколько задач
Простая:
Доказать тождество
$$(1+2)(1+2^2)(1+2^2^2)(1+2^2^3)...{(1+2^2^n)}=2^2^{n+1}-1$$
Посложнее:
Решить в целых числах уравнение
$$x^2+x=y^4+y^3+y^2+y$$
Часовой пояс: UTC UTC
Страница 5 из 8
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/