Комментарии 34
Сразу на ум приходит только за 7 раз.
5 — если время считать
Да, это дает решение за 7 забегов. А быстрее можно?
Небольшая неточность: третьей вполне может оказаться 2. Но это неважно.
Небольшая неточность: третьей вполне может оказаться 2. Но это неважно.
Нельзя. Пусть есть стратегия за 6 измерений. Введем множество помеченных элементов S. Изначально оно пусто. При каждом измерении будем выбирать порядок элементов такой, что все помеченные элементы идут после не помеченных и он не противоречит другим измерениям. При этом все элементы кроме первого помечаем. Тогда на каждом шаге множество S не может увеличивать более чем на 4 элемента и легко видеть, что каждый элемент не из S можно быть первым. Значит при каждом измерении размер S увеличивается ровно на 4, чтобы в конце стало 6*4=24 помеченных элемента (в противном случае первый элемент определяется не однозначно).
Добавим теперь дополнительное условие. Если 6 измерение содержит не помеченный элемент, который был первым в 5-том измерении, то он является первым и в 6 измерении.
Поскольку S каждый раз увеличивается на 4 элемента, в каждом измерении у нас 5 не помеченных элементов. Перед 5 измерением у нас 9 непомеченных элементов. 5 измерении сравнивает 5 из них и остается 5 непомеченных элементов. Они сравниваются в 6 измерении. Заметим теперь, что второй элемент определяется не однозначно. Это может быть второй в 6 измерении и второй в 5 измерении.
Действительно, оба этих элемента во всех предыдущих измерениях выходили первыми, поскольку они не помеченны перед 5 измерением. И для обеих единственная оценка сверху это то, что они меньше первого элемента в 5 и 6 измерении соответственно (который один и тот же в виду введенного нами дополнительного условия).
Добавим теперь дополнительное условие. Если 6 измерение содержит не помеченный элемент, который был первым в 5-том измерении, то он является первым и в 6 измерении.
Поскольку S каждый раз увеличивается на 4 элемента, в каждом измерении у нас 5 не помеченных элементов. Перед 5 измерением у нас 9 непомеченных элементов. 5 измерении сравнивает 5 из них и остается 5 непомеченных элементов. Они сравниваются в 6 измерении. Заметим теперь, что второй элемент определяется не однозначно. Это может быть второй в 6 измерении и второй в 5 измерении.
Действительно, оба этих элемента во всех предыдущих измерениях выходили первыми, поскольку они не помеченны перед 5 измерением. И для обеих единственная оценка сверху это то, что они меньше первого элемента в 5 и 6 измерении соответственно (который один и тот же в виду введенного нами дополнительного условия).
Великолепно. Существенно красивее, чем бывшее у меня доказательство.
Это не правильное доказательство. Из него следует, что 3 лучших нельзя определить даже если повезет. Но это не так. Пусть элементы на самом деле упорядочены как 1..25. Измерим 1,2,3,4,5; 5,6,7,8,9; 9,10,11,12,13;…; 21,22,23,24,25. Тогда из полученной информации однозначно следует, что 3 максимальных — это 23, 24, 25.
Тут есть ошибка. " Если мы из компоненты А взяли не минимальный элемент для 6го забега и этот элемент оказался максимальным в 6м забеге, то мы никак не можем определить, входит ли минимальный элемент компоненты А в искомое множество 3х минимальных.". Пусть A состоит из 5 элементов и мы выбрали средний (а в остальных — максимальные). Если он оказался максимальным, то 3 элемента выше него — и есть тройка максимальных. Т.е. тройка определяется однозначно.
За 5 итераций можно установить быстрейших лошадей в каждой из пятерок. За шестую итерацию можно установить тройку лидеров из этой пятерки.
За 6 итераций однозначно мы можем говорить только за самую быструю лошадь из всех 25. Остальные 4 могут оказаться медленнее каких-либо лошадей из отсеявшихся 20.
Пример: допустим так сложилось, что в первую пятерку выбились все самые быстрые лошади. Соответственно в остальных 4-х пятерках лошади посредственные. Мы провели 5 забегов этих 5 пятерок, и выявили 5 лидеров, по одному в каждой пятерке. 4 самых сильных лошади, таким образом, отсеялись и дальше они в забегах не участвуют, хотя они победили бы лидеров из остальных 4-х пятерок.
Более достоверный результат будет, если брать по 3 успешных лошади из каждой тройки, получим 15 лошадей для второго раунда. Снова по 3 лошади лидера, итого 9. Еще 2 забега. По 2 лошади лидера. И последний забег.
Итого 1 забегов и мы имеем 3 лошади лидера с относительно весьма низкой вероятностью погрешности.
За 6 итераций однозначно мы можем говорить только за самую быструю лошадь из всех 25. Остальные 4 могут оказаться медленнее каких-либо лошадей из отсеявшихся 20.
Пример: допустим так сложилось, что в первую пятерку выбились все самые быстрые лошади. Соответственно в остальных 4-х пятерках лошади посредственные. Мы провели 5 забегов этих 5 пятерок, и выявили 5 лидеров, по одному в каждой пятерке. 4 самых сильных лошади, таким образом, отсеялись и дальше они в забегах не участвуют, хотя они победили бы лидеров из остальных 4-х пятерок.
Более достоверный результат будет, если брать по 3 успешных лошади из каждой тройки, получим 15 лошадей для второго раунда. Снова по 3 лошади лидера, итого 9. Еще 2 забега. По 2 лошади лидера. И последний забег.
Итого 1 забегов и мы имеем 3 лошади лидера с относительно весьма низкой вероятностью погрешности.
пардон, «по 3 успешных лошади из каждой пятерки».
Итого 11 забегов…
Великолепно! Какая-то вероятность погрешности (притом, что в задаче просят определить достоверно). И 11 забегов, хотя очевидный метод (5 забегов, потом бегут лидеры, потом лидера предыдущего забега заменяем на следующего из той же пятерки, потом еще раз) дает 8 забегов.
Увы, но я не улавливаю алгоритма. И не уверен что все возможные варианты распределения скоростных характеристик лошадей, при отсутствии критерия оценки кроме как относительного порядка финиширования лошадей (т.е. невозможности сравнения кроме как в рамках забега), за 8 забегов вообще возможно определить.
Выше в комментариях есть алгоритм за 7 (он тоже тривиален) и доказательство, что быстрее нельзя.
За 8 делаем так: сначала сравниваем по 5. Потом бегут 5 лидеров, победитель — быстрейший среди всех. Потом бегут те же, кроме чемпиона, которого заменяем на второго из той же пятерки. Победитель — второй по скорости среди всех. Заменяем его на следующего за ним из той же пятерки — победитель этого забега — 3е абсолютное место.
За 8 делаем так: сначала сравниваем по 5. Потом бегут 5 лидеров, победитель — быстрейший среди всех. Потом бегут те же, кроме чемпиона, которого заменяем на второго из той же пятерки. Победитель — второй по скорости среди всех. Заменяем его на следующего за ним из той же пятерки — победитель этого забега — 3е абсолютное место.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Скачки