шедевры олимпиадной математики 1

[rus4]

Мне редко нравятся олимпиадные задачи по математике, но бывает что конкретно торкает. Эта среди моих самых фаворитов. Источник - забыл какая именно иранская студенческая олимпиада. Сколько раз где я её ни давал, ни разу ещё никто не решил. Сам тоже не решил в своё время

Comments

[plinioseviltwin]

А можно несколько уточняющих вопросов:
1. Случайные баллы за конкретную задачу одинаковы для всех студентов или случайное число выбирается отдельно для каждого студента?
2. За невыполненное задание начисляется 0 баллов?
3. Вас торкнуло после того, как Вы решили/узнали решение или до, сразу после понимания условия?

[rus4]

1. Конечно, для всех студентов одинаковое. Как объяснить студентам, что одному за решенную задачу номер 3 стоит 3 балла, а у другого 18?!

2. Да.

3. Условие просто понравилось, и решать понравилось, а решение вообще.

[anonymous]

Это называется "лемма об изоляции", довольно известный технический инструмент в компьютер сайнс. Её доказали Mulmuley и двое Vazirani в 1980-х. Позднее очень элегантное альтернативное доказательство придумал Spenser.

[rus4]

О, спасибо!

[a_konst]

Непонятны кванторы.
В вопросе "вероятность не менее 1/2" - это из какого набора вариантов?
Как распределяются вероятности решения разных задач студентами?
Или надо доказать, что при любом фиксированном наборе решенных задач(удовлетворяющих условию) вероятность не менее 1/2, а случайного в задаче - только распределение баллов за задачи?

[rus4]

Да, кто что решил - детерминированно, а случайны только баллы за задачи.