Мне кажется, было бы интересно задать ЕМУ вопрос, который когда-то самого интересовал и до ответа на который когда-то с трудом докопался. Насколько ОНО могло бы тогда помочь? Вот я вспомнил одну свою задачку. Будем играть в такую игру (сам с собой). Перед нами 5 лунок, в которых могут лежать камешки. И есть неограниченный запас камешков. Одним ходом можно сделать следующее: 1) взять новый камешек и добавить его в одну из лунок, после чего 2) переложить любое число камешков из одних лунок в другие. Ход допустимый, если новое состояние не может быть получено ни из одного из старых посредством добавления какого-то числа камешков (без перекладываний других камешков). Пусть изначально в первой лунке один камешек, в остальных ничего нет. Вопросы: 1. Возможна ли бесконечная последовательность допустимых шагов? 2. Если нет, то существует ли сколь угодно длинная последовательность допустимых шагов? 3. Если нет, то какое максимальное число допустимых шагов можно выполнить из данной начальной позиции? -------------------------------------- Во-первых, надо, чтобы оно вопрос поняло. Это уже требует определенного интеллекта. Ну, а далее интересно, что оно ответит.
Let's consider such a situation. Before us are 4 holes in which pebbles can lie. And there is an unlimited supply of pebbles. In one step, one can do the following: 1) take a new pebble and add it to one of the holes, after which 2) transfer any number of pebbles from one hole to another. A step is admissible if a new state cannot be obtained from any of the old ones by adding a certain number of pebbles (without rearranging other pebbles). Suppose initially there is one pebble in the first hole, and there is nothing in the rest. Questions: 1. Is an infinite sequence of admissible steps possible? 2. If not, is there an arbitrarily long sequence of admissible steps? 3. If not, what is the maximum number of steps that can be taken from a given starting position? 4. Is there a 100-step sequence of admissible steps? Вот первый ответ: <<< 1. Yes, an infinite sequence of admissible steps is possible. One possible strategy is to repeatedly transfer one pebble from the first hole to the second hole, then add a new pebble to the first hole. This generates an infinite sequence of distinct states, as no state can be reached by adding a certain number of pebbles to a previous state. For example, the first few steps would look like: - Step 1: 1 0 0 0 (initial state) - Step 2: 0 1 0 0 - Step 3: 1 1 0 0 - Step 4: 0 2 0 0 - Step 5: 1 2 0 0 - Step 6: 0 3 0 0 - Step 7: 1 3 0 0 - ... 1. Yes, there is an arbitrarily long sequence of admissible steps. This can be achieved by repeatedly transferring pebbles from the first hole to the other holes, then adding a new pebble to the first hole. At each step, the number of pebbles in the first hole will increase by one, while the other holes will have a varying number of pebbles. Since there are an unlimited number of pebbles, this process can continue indefinitely. 1. The maximum number of steps that can be taken from a given starting position is 4. There are only 4 distinct states that can be reached from the initial state, which are: - 1 0 0 0 (initial state) - 0 1 0 0 - 0 0 1 0 - 0 0 0 1 After reaching any of these states, no more admissible steps are possible, as any further addition or transfer of pebbles will result in a state that can be obtained by adding a certain number of pebbles to a previous state. 1. No, there is no 100-step sequence of admissible steps. Since the maximum number of steps from the initial state is 4, it is not possible to reach a state that requires more than 4 steps to reach. Therefore, it is not possible to have a 100-step sequence of admissible steps. Меня восхитило, что ОНО само изобрело языковую модель ситуации в форме вектора из 4х целых неотрицательных чисел. В остальном все очень тупо. Я долго вдалбливал, что один шаг состоит (сразу) из добавления одного камешка и перекладывания некоторых камешков. ОНО упорно делило их на 2 шага. Результат перекладываний почти всегда показывался неверно. До понимания условия допустимости вообще речь не доходит, хотя ОНО и пыталось им "жонглировать". Но ситуация, по-моему, интересна как тест, поскольку показывает ее (не)способность строить и манипулировать простыми моделями, не требующими специальных познаний. До математического содержания вопросов ЕМУ, конечно, еще очень далеко (отрицательный ответ на вопрос 1 дает Лемма Хигмана). Задав число лунок 4 вместо 5, я все же надеялся, что поняв задачу, оно сможет ее решить тупым перебором (правильный ответ на третий вопрос - 12). А для 5 перебор "посадил" бы все сервера. PS. Заметил свою неточность в английской постановке: во 2-м полушаге допустимо перекладывать любое число камешков из любого числа лунок в другие лунки (а не из одной в одну другую). Но вроде это не отразилось бы на результатах. PPS. Исправленная версия постановки: Let's consider such a situation. Before us are 4 holes in which pebbles can lie. And there is an unlimited supply of pebbles. In one step, you can do the following: 1) take a new pebble and add it to one of the holes, after which 2) transfer any number of pebbles from some holes to others. A step is valid (admissible) if a new state cannot be obtained from any of the old ones by simply adding a certain number of pebbles (without rearranging other pebbles). Note that all pebbles are equal among each other (indistinguishable). Suppose that initially there is one pebble in the first hole, and there is nothing in the rest ones. Questions are: 1. Is an infinite sequence of valid steps possible? 2. If not, is there an arbitrarily long sequence of valid steps? 3. If not, what is the maximum number of valid steps (as a sequence) that can be taken from this starting position? 4. Is there a 100-step sequence of valid steps?
