2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 14:50 


26/08/18
10
Для простоты будем оперировать с множеством всех натуральных чисел и целочисленными последовательностями. Очевидно, туда входит бесконечно много подмножеств, содержащих последовательности.
Например, загадаем любую последовательность, которую возьмем с энциклопедии OEIS. Пусть это будет A005097 (абсолютно наугад выбрал). Это:
1, 2, 3, 5, 6, 8 , 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36, 39, 41, 44, 48, 50, ....
Нам это известно, другому человеку неизвестно ничего, в том числе и числа входящие в его ряд.

Можно ли найти эту последовательность, задавая вопросы на которые возможен только ответ ДА/НЕТ? Если можно, какие вопросы, и какой алгоритм должен быть? Если невозможно, то почему?

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 14:56 
Заслуженный участник
Аватара пользователя


18/09/14
5142
Ваш вопрос требует уточнения. Поскольку очевидно, что если спрашивающий задаст вопрос "верно ли, что загадана последовательность A005097?", он получит ответ "да", который окажется исчерпывающим :-)

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 14:56 
Заслуженный участник
Аватара пользователя


16/07/14
9263
Цюрих
Если разрешены только последовательности из OEIS - то очевидно можно: "это A000001?", "это A000002?", ..., "это A342859?".
Если разрешены произвольные последовательности - то за конечное число вопросов очевидно нельзя. За бесконечное - нужно уточнять протокол.

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:00 


26/08/18
10
Цитата:
верно ли, что загадана последовательность A005097?

Нет, нет. Такой вопрос некорректный, просто оттуда удобно брать последовательности. Тем более, их бесконечно много, легко можно придумать свою.

-- 26.03.2021, 14:03 --

mihaild в сообщении #1511312 писал(а):
Если разрешены только последовательности из OEIS - то очевидно можно: "это A000001?", "это A000002?", ..., "это A342859?".
Если разрешены произвольные последовательности - то за конечное число вопросов очевидно нельзя. За бесконечное - нужно уточнять протокол.


Последовательности произвольные. Но, я не уверен, что за конечное число вопросов нельзя найти ее. Самое главное - нужен алгоритм и правильные вопросы.

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:05 
Заслуженный участник
Аватара пользователя


18/09/14
5142
macdonalds в сообщении #1511317 писал(а):
Такой вопрос некорректный

Почему? Объясните, что Вы понимаете под "корректным" вопросом. Иначе говоря, вопросы какого типа разрешены.

-- 26.03.2021, 15:08 --

Объясните также, чего Вы ждёте от алгоритма: чтобы он гарантированно нашёл последовательность, или случайное её обнаружение тоже приветствуется?

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:09 
Заслуженный участник
Аватара пользователя


16/07/14
9263
Цюрих
macdonalds в сообщении #1511317 писал(а):
Но, я не уверен, что за конечное число вопросов нельзя найти ее.
Пусть мы задаем произвольное, но всегда конечное число вопросов. Сколько вариантов ответов мы можем получить? А сколько последовательностей существует?

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:19 


26/08/18
10
Mihr в сообщении #1511319 писал(а):
Объясните также, чего Вы ждёте от алгоритма: чтобы он гарантированно нашёл последовательность, или случайное её обнаружение тоже приветствуется?

Именно гарантированно.

Допустим, для последовательности выше можно легко сузить рамки, с помощь нескольких вопросов:
Содержит ли п-ь только нечетные числа?
Содержит ли п-ь только четные числа?
Содержит ли п-ь простые числа?
П-ь начинается с единицы?
В этой п-и однозначных чисел от 5 до 10?
В этой п-и двузначных чисел от 20 до 50?
и т.д.

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:21 
Заслуженный участник
Аватара пользователя


18/09/14
5142
macdonalds в сообщении #1511323 писал(а):
Именно гарантированно.

Тогда попробуйте ответить на вопросы mihaild.

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:33 


26/08/18
10
mihaild в сообщении #1511320 писал(а):
Пусть мы задаем произвольное, но всегда конечное число вопросов. Сколько вариантов ответов мы можем получить? А сколько последовательностей существует?

Предполагается, что последовательность, как бы это выразится, человечная что ли. В дебри бесконечностей и гуголов забредать не будем. Именно поэтому я и взял последовательность с OEIS.

-- 26.03.2021, 14:35 --

Давайте, если так проще: возьмем произвольную последовательность с сайта OEIS, можно ли ее найти с помощью логики, не задавая вопросов это A000001?", "это A000002?", ..., "это A342859?

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:38 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
macdonalds в сообщении #1511327 писал(а):
В дебри бесконечностей и гуголов забредать не будем. Именно поэтому я и взял последовательность с OEIS.
Ну так там большинство последовательностей как раз бесконечные.

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:42 


26/08/18
10
Aritaborian в сообщении #1511329 писал(а):
Ну так там большинство последовательностей как раз бесконечные.

Это разумеется. Но формулы их не бесконечные. Нет там дурацких формул вроде a(n) = 2n^43-n!, которую найти будет крайне трудно, там в основном короткие и компактные.

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:45 
Заслуженный участник
Аватара пользователя


18/09/14
5142
Если последовательность выбирается из фиксированного конечного множества последовательностей, то, разумеется, её можно выделить, используя конечное число вопросов. Зная объём этого множества последовательностей, легко оценить достаточное число вопросов.

-- 26.03.2021, 15:48 --

macdonalds в сообщении #1511330 писал(а):
Нет там дурацких формул вроде a(n) = 2n^43-n!

Формулы дурацкими не бывают. Вам всё-таки стоило бы уточнить, какие вопросы Вы считаете разрешёнными. Пока Вы на этот вопрос не ответили.

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:55 
Заслуженный участник
Аватара пользователя


16/07/14
9263
Цюрих
Ну если последовательность хотя бы арифметическая (вроде бы все последовательности с OEIS такие) - то, очевидно, можно. "Пусть $x$ - лексикографически наименьшая из самых коротких формул в алафвите [выбрать какой-нибудь хороший алфавит], задающих нашу последовательность. Верно ли, что $|x| < 1$? что $|x| < 2$? ...? [установили длину] Верно ли, что первый символ $x$ такой-то? ...".
macdonalds в сообщении #1511330 писал(а):
Нет там дурацких формул вроде $a(n) = 2n^{43}-n!$
Там есть последовательности, арифметические формулы для которых гораздо длиннее)

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:56 


05/09/16
12180
macdonalds в сообщении #1511317 писал(а):
Последовательности произвольные. Но, я не уверен, что за конечное число вопросов нельзя найти ее. Самое главное - нужен алгоритм и правильные вопросы.

Вы знаете, это немного напоминает изобретателей вечных двигателей, которым всегда не хатает хорошей смазки и инструментов выточить ровную втулку :)

 Профиль  
                  
 
 Re: Можно ли найти последовательность с помощью ДА/НЕТ?
Сообщение26.03.2021, 15:59 


26/08/18
10
Mihr в сообщении #1511332 писал(а):
Если последовательность выбирается из фиксированного конечного множества последовательностей, то, разумеется, её можно выделить, используя конечное число вопросов. Зная объём этого множества последовательностей, легко оценить достаточное число вопросов.

Ок, ок, я понял свою ошибку.

Mihr в сообщении #1511332 писал(а):
какие вопросы Вы считаете разрешёнными

Любые вопросы, на которые можно ответить ДА/НЕТ и которые определяют свойства членов, входящих в ряд этой целочисленной последовательности. Например, про четные/нечетные,/простые/фибоначи/и т.д. Наводящий вопрос, является ли это A005097, запрещен, потому что он сразу определяет конкретный ряд, а не его члены.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: mihaild


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group