2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Замкнутые пути в Z^n
Сообщение02.08.2016, 16:35 
Заслуженный участник


27/04/09
28128
Несложная. Рассмотрим граф из точек $\mathbb Z^n$, соединённых рёбрами тогда, когда одну можно получить из другой прибавлением единицы к одной из координат. Найдите длины всех возможных замкнутых путей, в которых никакие соседние $n+1$ вершин не лежат в одной гиперплоскости.

Может, найдёте решение покрасивее моего. :-) Если не будет в течение какого-то времени, выложу своё.

 Профиль  
                  
 
 Re: Замкнутые пути в Z^n
Сообщение03.08.2016, 16:39 


11/07/11
164
Можно уточнить понятие "соседние"?

 Профиль  
                  
 
 Re: Замкнутые пути в Z^n
Сообщение03.08.2016, 20:04 
Заслуженный участник


27/04/09
28128
Идущие непосредственно друг за другом в пути.

 Профиль  
                  
 
 Re: Замкнутые пути в Z^n
Сообщение04.08.2016, 08:14 


11/07/11
164
Тогда ответ - все кратные 2n. Выберем направление обхода пути и рассмотрим рёбра как векторы. Чтобы выполнялось условие, необходимо, чтобы среди n последовательных рёбер хотя бы раз встретился вектор, коллинеарный каждому базисному вектору. Если рассмотреть путь в проекции на какую-нибудь ось, становится понятно, что векторы, коллинеарные каждому базисному вектору, должны встречаться в пути чётное количество раз. Таким образом, общее количество рёбер пути должно делиться на 2n. Для каждого натурального k нетрудно построить пример пути из 2nk рёбер - сначала k раз идём поочерёдно в направлении всех базисных векторов, затем k раз идём поочерёдно в направлении векторов, противоположных базисным.

 Профиль  
                  
 
 Re: Замкнутые пути в Z^n
Сообщение04.08.2016, 17:31 
Заслуженный участник


27/04/09
28128
Ага.

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

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



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

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


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

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