Найти минимальное количество

[Ilya83]

Генерируются алгоритмы, выполняющие одну из 7 задач. Генерация алгоритмов закончится, когда найдется хотя бы одна задача, которую выполняет хотя бы 7 различных алгоритмов. Найти минимальное количество алгоритмов.

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

Тогда получается, что необходимо $7!$ алгоритмов. Однако в решении, в первом шаге предлагается использовать формулу $7(7-1)$, что является $7P2$. Согласно теории, формулу $7P2$ используют, когда необходимо упорядочить только часть из набора.

Я не понимаю, какой набор имеется ввиду задач или алгоритмов и почему выбирается только 2 из 7. Что в данном случае 2 ?

[Mihr]

Условие Вашей задачи звучит не очень чётко.

Ilya83 в сообщении #1730100 писал(а):

Найти минимальное количество алгоритмов.

Это можно понимать двумя способами:
1. Найти минимальное количество алгоритмов, при котором процесс может остановиться.
2. Найти минимальное количество алгоритмов, при котором процесс гарантированно остановится.
Ответ на первый вопрос очевиден: если все алгоритмы будут решать одну и ту же задачу, то, очевидно, после генерации 7-го алгоритма процесс остановится.
Второй вопрос не намного сложнее: достаточно вспомнить принцип Дирихле.
Оба ответа гораздо меньше, чем $7!$.

[Booker48]

Точную формулировку условия можете привести?
Потому что по этой формулировке минимальное количество сгенерированных алгоритмов равно 7 (семи).

[Ilya83]

Цитата:

Точную формулировку условия можете привести?

Без купюр

Цитата:

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

Booker48 Почему 7? 1 алгоритм решает 1 из 7 задач. Значит второй алгоритм будет решать 1 из 6....
Т.е. из всего набора $n(n-1)(n-2)...$ гарантированно будут алгоритмы, которые решают 1 задачу.
Или я не правильно понял условие задачи?

[mihaild]

Ilya83 в сообщении #1730105 писал(а):

Значит второй алгоритм будет решать 1 из 6

Нет, не значит.

Ilya83 в сообщении #1730105 писал(а):

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

Формулировка так себе. Но я бы сказал, что самая разумная интерпретация - это что неизвестно, какой алгоритм какую задачу решает, и нам нужно их генерировать, пока мы не будем уверены, что хотя бы какая-то задача решена достаточное количество раз.
Т.е. второй вариант Mihr.

[Ilya83]

Цитата:

Оба ответа гораздо меньше, чем $7!$

Я на это указал. В решении задачи предлагается использовать формулу $7(7-1)$. А это по сути $7P2$. Я не понимаю, как я могу применить формулу $7P2$ к данной задаче.

Цитата:

принцип Дирихле

Это про голубей? Спасибо. Попробую применить этот принцип к данной задаче.

[Booker48]

Ilya83 в сообщении #1730105 писал(а):

Без купюр

Цитата:

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

В такой постановке соглашусь с mihaild и Mihr.
Если сгенерированы 42 задачи, то существует вариант, когда каждая из семи задач решена шестью различными алгоритмами.

[Ilya83]

Цитата:

Если сгенерированы 42 задачи, то существует вариант, когда семь задач решены шестью различными алгоритмами.

Я до рассмотрения данного случая еще не дошел. Тут же противоречие. В условии сказано, что алгоритм решает только 1 задачу. Как может 6 алгоритмов решать 7 задач? Значит какой-то алгоритм решает сразу 2 задачи? Противоречие.

[Mihr]

Ilya83 в сообщении #1730109 писал(а):

Как может 6 алгоритмов решать 7 задач?

Имеется в виду:
- первая задача решена 6 раз (6-ю различными алгоритмами)
- вторая задача решена 6 раз (6-ю различными алгоритмами)
...
- седьмая задача решена 6 раз (6-ю различными алгоритмами)
Таким образом, сгенерированы уже 42 разных алгоритма, и каждая задача решена не более шести раз (а точнее, ровно 6 раз).
Очередной (43-й) алгоритм решит какую-то задачу в седьмой раз, и процесс остановится.

[Booker48]

Ilya83 в сообщении #1730109 писал(а):

В условии сказано, что алгоритм редает только 1 задачу. Как может 6 алгоритмов решать 7 задач? Значит какой-то алгоритм решает сразу 2 задачи? Противоречие.

Нет противоречия. Пусть генерируемые алгоритмы пронумерованы последовательно.
Тогда есть вариант:
1й алгоритм решает задачу 1
2й ------------------------ 2
3й ------------------------ 3
4й ------------------------ 4
5й ------------------------ 5
6й ------------------------ 6
7й ------------------------ 7

8й алгоритм решает задачу 1
9й ------------------------ 2
10й ------------------------ 3
11й ------------------------ 4
12й ------------------------ 5
13й ------------------------ 6
14й ------------------------ 7

----------

36й алгоритм решает задачу 1
37й ------------------------ 2
38й ------------------------ 3
39й ------------------------ 4
40й ------------------------ 5
41й ------------------------ 6
42й ------------------------ 7

-- добавлено через 2 минуты --

Mihr
Сорри, уже набрал, было бы обидно не отправить. )))

[Ilya83]

Booker48, Mihr, mihaild
Спасибо Вам за потраченное время. Дальше постараюсь сам разобраться.

[Евгений Машеров]

Сбивает в условии с толку то, что две разные семёрки - число задач n и число решений какой-то задачи m. Поэтому возникает впечатление, что в ответе фигурирует число размещений.
Вообще для подобного анализа, на "гарантированное время" Кнут предложил использовать дьяволов (не путать с демонами - демоны служат, а дьяволы пакостят). Которые вмешиваются так, чтобы максимально замедлить работу. В данном случае подталкивая алгоритм, чтобы он решал любую задачу, но не ту, где уже 6 решено. В результате каждая задача имеет $m-1$ решение, всего $n(m-1)$ вызовов алгоритма, и новый даст m-тое решение какой-либо из задач.
Подход Кнута в первом томе "Искусства программирования".

[Ilya83]

Mihr, подскажите пожалуйста, подходит ли такое решение данной задачи:

Допустим всего 2 задачи и для каждой задачи существует 2 варианта выпадения алгоритма (решено/не решено). Значит для 2 задач существует $\frac{2!}{(2-2)!}$ вариантов алгоритмов. Следовательно, если от нас требуется $n$ вхождений, решение можно записать формулой $\frac{n!}{(n-2)!}+1$

[Mihr]

Ilya83, извините, я Вас очень плохо понял. Вас что-то не устроило в объяснениях выше? Ведь Евгений Машеров уже объяснил, что размещения здесь ни при чём. Далее, как Вы собираетесь обобщать? Вы пишете:

Ilya83 в сообщении #1730510 писал(а):

Допустим всего 2 задачи и для каждой задачи существует 2 варианта выпадения алгоритма (решено/не решено).

А для $n$ задач? Должно быть $n$ возможностей, что ли? То есть, помимо "решено/не решено" появляются какие-то новые возможности? Оставьте этот путь, он какой-то очень странный. Лучше разберитесь в том, что написано в теме выше. Там всё очень просто, правда. Не пытайтесь пристегнуть сюда формулу для числа размещений, она не имеет отношения к данной задаче.

[Евгений Машеров]

Извините, соврал. Про "дьяволов" у Кнута в третьем томе, раздел 5.3.2, где он оценивает эффективность сортировки в худшем случае.