2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Доказательство для активации битов
Сообщение19.11.2020, 11:27 
Аватара пользователя


22/11/13
498
Имеем бинарный массив длины $2n$. Мы можем активировать любые биты. При активации бита соседние биты меняют свои значения $0\to1$, $1\to0$. Наша цель - превратить исходный бинарный массив в массив из одних только единиц через активацию битов. Доказать, что при любом значении бинарного массива это возможно максимум за $2n$ активаций.

Имеем бинарный массив длины $4n+1$. Можем активировать любые биты и т.д. Доказать, что массив можно привести к массиву из одних только единиц если значение массива принадлежит последовательности A158705 (положительные целые с нечетным количеством нечетных степеней $2$-ки в двоичной записи $n$) максимум за $4n+1$ активаций. Доказать также, что это невозможно, если значение массива принадлежит последовательности A158704 (положительные целые с четным количеством нечетных степеней $2$-ки в двоичной записи $n$).

Имеем бинарный массив длины $4n+3$. Можем активировать любые биты и т.д. Доказать, что массив можно привести к массиву из одних только единиц если значение массива принадлежит последовательности A158704 максимум за $4n+1$ активаций. Доказать также, что это невозможно, если значение массива принадлежит последовательности A158705.

 Профиль  
                  
 
 Re: Доказательство для активации битов
Сообщение19.11.2020, 12:19 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Не совсем понятно, что значит "активировать бит".
Можно на примере показать? Вот у нас массив из четырёх элементов: 0101.
Что будет, если мы "активируем" первый элемент? А если второй? третий? четвёртый?

Т.е. понятно, что происходит с соседними элементами (но тоже не до конца: вдруг элементы "циклически заворачиваются" и соседом справа для самого правого будет самый левый?).
А сам активируемый бит, он не меняется? устанавливается в 1? или меняется на противоположный?

 Профиль  
                  
 
 Re: Доказательство для активации битов
Сообщение19.11.2020, 17:05 
Аватара пользователя


22/11/13
498
Массив из 4-х элементов, 0101. При активации

1-го бита 0001
2-го бита 1111
3-го бита 0000
4-го бита 0111

Элементы циклически не заворачиваются. Сам активируемый бит не меняется.

 Профиль  
                  
 
 Re: Доказательство для активации битов
Сообщение19.11.2020, 17:20 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
То есть мы можем инвертировать второй бит, предпоследний, и два, отстоящих друг от друга на один?
Это получается вопрос о разрешимости в $\mathbb Z_2$ системы уравнений с явно выписываемой матрицей. Ну и при нечетной длине письма у четные и нечетные разряды меняются независимо.

 Профиль  
                  
 
 Re: Доказательство для активации битов
Сообщение20.11.2020, 06:42 
Аватара пользователя


22/11/13
498
Если элементы циклически заворачиваются, т.е. у первого элемента соседи это второй и последний, а у последнего - предпоследний и первый, то для бинарного массива длины $2n+1$ массив можно привести к массиву из одних только единиц если значение массива принадлежит последовательности A000069 (числа с нечетным числом единиц в их $2$-ном разложении). Для $4n$ и $4n+2$ в энциклопедии последовательностей не нашлось.

 Профиль  
                  
 
 Re: Доказательство для активации битов
Сообщение20.11.2020, 10:03 
Аватара пользователя


22/11/13
498
mihaild в сообщении #1493287 писал(а):
Это получается вопрос о разрешимости в $\mathbb Z_2$ системы уравнений с явно выписываемой матрицей. Ну и при нечетной длине письма у четные и нечетные разряды меняются независимо.

Можно чуть подробнее?

Мой метод нахождения результата состоит в следующем:
1) генерирую в Excel все перестановки длины $n$
2) под каждую перестановку создаю массив длины $n$ из единиц
3) с помощью нехитрых формул активирую бит, номер которого - первый элемент перестановки
4) сохраняю значения всех получившихся бинарных массивов, удаляю дубликаты
5) аналогично активирую бит, номер которого - второй элемент перестановки, далее аналогично п.4
6) продолжаю активировать биты, по итогам все сохраненные значения помещаю в один столбец, удаляю дубликаты, имею:
а) все числа для массивов длины $2n$
б) A158705 для массивов длины $4n+1$
в) A158704 для массивов длины $4n+3$
г) A000069 для массивов длины $2n+1$ (с небольшой корректировкой нехитрых формул)

Идеей для этой конструкции послужил 21-ый уровень логической игры yellow от разработчика Bart Bonte. Между делом, всем рекомендую. Игра примечательна тем, что в ней сперва необходимо разобраться что от нас требуется, а уже потом как это, собственно, сделать. У этого разработчика целая серия игр с названиями цветов из которых можно красть идеи черпать вдохновение. Так, 49-ый уровень игры red, с которой я познакомился весной 2018 года, сподвигнул меня на экспериментальные исследования, опубликованные в темах Описание подхода получения результата и восполнение пробела, Подкрепление опытных результатов логикой, Доказательство рекуррентной формулы.

 Профиль  
                  
 
 Re: Доказательство для активации битов
Сообщение20.11.2020, 11:59 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
kthxbye в сообщении #1493379 писал(а):
1) генерирую в Excel все перестановки длины $n$
Причем тут перестановки?
kthxbye в сообщении #1493379 писал(а):
Можно чуть подробнее?
Вы знаете, что такое система линейных уравнений?
Очевидно, что порядок активации битов неважен (активация сначала $a$, потом $b$ или сначала $b$ потом $a$ дает один и тот же результат), и что активировать один бит больше одного раза не надо. Давайте заведем $n$ бинарных переменных $a_i$, где $a_i = 1$ если мы будем активировать $i$-й бит, и $a_i = 0$ иначе. Как выглядит условие "мы в итоге получаем вот такое число"?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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