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

bot · Сообщение **bot** » 07 июн 2007, 18:05

andrej163 писал(а):Source of the post
...

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

Natrix · Сообщение **Natrix** » 07 июн 2007, 21:37

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 менял - ПРОИГРАЛ. Поменял - ВЫИГРАЛ

andrej163 · Сообщение **andrej163** » 07 июн 2007, 21:41

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

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

a_l_e_x86 · Сообщение **a_l_e_x86** » 07 июн 2007, 21:56

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

andrej163 · Сообщение **andrej163** » 07 июн 2007, 21:57

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

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

Pavlukhin · Сообщение **Pavlukhin** » 08 июн 2007, 01:08

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

bot · Сообщение **bot** » 08 июн 2007, 14:56

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}$ , очередной (то есть второй) вычисляет свой цвет и, называя его, передаёт эту информацию наверх ...

Pavlukhin · Сообщение **Pavlukhin** » 08 июн 2007, 16:18

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

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

Для k цветов то же самое (только одним пальцем уже не обойтись):
Bce цвета занумеруем числами , a n умников в порядке их очерёдности занумеруем от 0 до n-1.
Цвет шапки на 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}$ , остальные узники услышав вычисляют $S_2 \pmod{k}$ , очередной (то есть второй) вычисляет свой цвет и, называя его, передаёт эту информацию наверх ...

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

Для k цветов то же самое (только одним пальцем уже не обойтись):
Bce цвета занумеруем числами , a n умников в порядке их очерёдности занумеруем от 0 до n-1.
Цвет шапки на 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}$ , остальные узники услышав вычисляют $S_2 \pmod{k}$ , очередной (то есть второй) вычисляет свой цвет и, называя его, передаёт эту информацию наверх ...

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

bot · Сообщение **bot** » 08 июн 2007, 16:30

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

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

a_l_e_x86 · Сообщение **a_l_e_x86** » 16 июн 2007, 11:42

Предлагаю еще несколько задач
Простая:
Доказать тождество
$(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$$

yourdomain.com