Портал Естественных Наук, версия 1.1

Ау, если кто из постоянных участников здесь бывает- самое время снова включиться. Потому что ранее такие олимпиады тут щелкали как орешки. 8 задач олимпиады даны в вордовском файле , пришедшем из жюри. Но не удивляйтесь если часть ответов неправильные, жюри ведь не все должно состоять из классных специалистов, их повсюду не хватает. Особенно поразила задача 8 на алгоритм упорядочения , и ее ответ

Номер 8 видится какой-то нетривиальной.
Понятно, что после каждого нового эксперимента можно для каждой позиции сузить диапазон поиска.
И желательно на следующем этапе его ещё сузить, подставив значение внутри диапазона (в идеале бинарный поиск).
Но там же не любые независимые значения, а перестановки.

Наверно можно варианты малой длинны рассмотреть (2, 3, 4) для начала. Может идеи какие даст.

zykov писал(а):Номер 8 видится какой-то нетривиальной.

Предагаю первый ход {50,50,...} 100 раз. В нашей последовательности равные значения не запрещаются. При этом будет одно попадание, а у каждой иной позиции диапазон сузится до 49 или 50 единиц. Далее с такими и действовать единообразно.

Или вот задание 5. Подставляю первый ответ жюри - левая и правая часть уравнения отличаются на пи. Второй ответ-аналогично. Отсюда вывод что решений у уравнения нет)

Ian писал(а):Source of the post Предагаю первый ход {50,50,...} 100 раз.

Так да, будет просто бинарный поиск.
Но я понял так, что [math]y тоже должен быть перестановкой. Т.е. "все 50" не подходит.

Задание 8. Про последовательность [math]X=(x_1,…,x_{100}) известно, что она состоит из всех натуральных чисел от 1 до 100, переставленных в некотором порядке. Мы должны узнать этот порядок. За один шаг можно выписать любую, также состоящую из чисел от 1 до 100, последовательность [math](y_1,…,y_{100}), про каждый член [math]y_i (i=1,...,100) которой нам сообщат, какое из соотношений [math]y_i>x_i, [math]y_i<x_i или [math]y_i=x_i имеет место. За какое наименьшее число шагов можно наверняка определить X?

Сказано "также состоящую из чисел от 1 до 100" а не "также состоящую из чисел от 1 до 100, переставленных в некотором порядке". И как должен понять школьник...От такой мелочи зависит, ответ 6 или 50. И что за 50 шагов при Вашей трактовке условия? И даже с доказательством что меньше 50 нельзя

Еще задание 1 связано с тонкостями русского языка. В ней четко спрашивается ответ в дробях. А жюри дает ответ в процентах. Мало того, всем, кто дал ответ в дробях, решение засчитали как неверное. Какой то разлад между тем кто составлял задачи (действительно хорошие) и тем кто готовил решения.

Ian писал(а):Source of the post Сказано "также состоящую из чисел от 1 до 100"

Я понимаю, что "также" - "также как и [math]x".
Кроме того, если не накладывать ограничение перестановок, то становится как-то тривиально.
Т.е. "если трактовка делает олимпиадную задачу тривиальной, то это неверная трактовка".

Вставлю сюда картинки, чтобы в документ не лазить.

Ian писал(а):Source of the post мало того, всем, кто дал ответ в дробях, решение засчитали как неверное.

Если в решении ошибок нет и ответ достаточно точный, то какая разница - проценты это или ещё какой другой формат.
Надо оспаривать, если снизили только из-за формата записи.

zykov писал(а):

Ian писал(а):Source of the post Сказано "также состоящую из чисел от 1 до 100"

Я понимаю, что "также" - "также как и [math]x".
Кроме того, если не накладывать ограничение перестановок, то становится как-то тривиально.
Т.е. "если трактовка делает олимпиадную задачу тривиальной, то это неверная трактовка".

Не такой уж тривиальной. Кроме организации двоичного поиска, надо будет доказать что за 5 вопросов (в виде произвольных последовательностей) невозможно. А тут не сходится, [math]100!<2^{400}\cdot 3^{100} и даже [math]100!<2^{466}\cdot 3^{34} , надо глубже копать

Ian писал(а):Source of the post Кроме организации двоичного поиска, надо будет доказать что за 5 вопросов

А может и можно...

Это если игнорировать, что [math]x - перестановка, то будет просто 100 независимых бинарных поисков на 6 шагов.
Но вот если где-то уже нашли, что в такой-то позиции такое-то число, то уже известно, что в другой позиции этого числа быть не может.
Скажем, если после 5-ого шага для 50 позиций уже нашли, а ещё для 50 нужен тест из двух возможных вариантов, и если везде из этих двух вариантов второй отпадает, т.к. уже занят на другой позиции, то и 6-ой шаг не нужен.

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