2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Задача про единицы
Сообщение26.06.2014, 08:23 


21/06/11
71
Доброго времени суток, уважаемые математики. Помогите, пожалуйста, решить такую задачу. В ряд, в произвольном порядке, записаны 1 или -1, (всего 20). Разрешается изменить знак у любых трех соседних чисел. При какой расстановке чисел можно (или нельзя) получить в ряду все единицы?

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


09/02/14

1377
А в каком виде надо дать ответ? По любому данному ряду можно легко сказать, можно ли получить все единицы или нет, так как, по сути, это система (не очень сложных) линейных уравнений над $\mathbb{F}_2$.

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 08:38 


21/06/11
71
В любом. Желательно наиболее простом.

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 08:41 


08/05/08
593
Откуда задача?
Определить действительно просто, тк доступные операции коммутируют и имеют порядок 2 (из чего можно ванговать, что ровно четверть таких последовательностей решаются). Просто тут ругаются на полное решение, а в олимпиадных задачах ругаются на задачи с действующей олимпиады

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 08:46 


21/06/11
71
это не задача, это тупиковый момент в размышлениях.

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 08:49 


08/05/08
593
Ну вот не знаю, поможет ли это, или это вам и так понятно, но...
Если просто абсолютно тупо слева (или справа) выстраивать единицы, то если последовательность решаема, она обязательно решится таким способом
То есть ищем первую слева неправильную цифру - переворачиваем от нее вправо 3 цифры идт итп. Если последовательность в принципе решаема, то такой алгоритм ее обязательно решит (это следует из коммутативности операции и того, что ее порядок равен 2)

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 08:52 


21/06/11
71
Это и так понятно. Но хотелось бы узнать какие-то начальные условия.

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


09/02/14

1377
Последовательность решаема тогда и только тогда, когда удовлетворяет условиям
$$\sum_{t=1}^{17} F_t x_{17-t+1} + \sum_{t=1}^{18} F_t x_{18-t+1} \equiv x_{19} (\operatorname{mod} 2)$$
$$\sum_{t=1}^{18} F_t x_{18-t+1} \equiv x_{20} (\operatorname{mod} 2)$$
Где $F_1 = 1, F_2 = 1, F_k = F_{k-1} + F_{k-2}$, а $x_i = 0$ если на $i$-ом месте стоит $1$ и $x_i = 1$ если на $i$-ом месте стоит $-1$.
Нумерация с единицы.

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 09:10 


21/06/11
71
kp9r4d

Спасибо большое!!! Буду разбираться.

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 23:21 


29/08/11
1137
kp9r4d, возможно ли такой метод обобщить для следующей задачи:

В таблице 20 на 14 произвольно записаны числа 1 или -1. За шаг возможно изменить числа на противоположные в квадрате 2 на 2 или 3 на 3. Можно ли сделать так, чтобы таблица состояла только из 1?

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 23:27 
Заслуженный участник


27/04/09
28128
Все эти преобразования тоже коммутируют.

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение26.06.2014, 23:50 


29/08/11
1137
arseniiv, просто эта задача эквивалентна этой topic85365.html

Не могу понять, как соотнести эти решения...

 Профиль  
                  
 
 Re: Задача про единицы
Сообщение27.06.2014, 00:05 
Заслуженный участник


27/04/09
28128
Там, с первого взгляда, аналогичные суммы по модулю 2.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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