2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: 1000 городов, одностороннее движение.
Сообщение29.08.2014, 17:11 
Аватара пользователя

(function)

Вообще-то мы пытались добиться логики именно от ТС, а не от вас ... :-)

 
 
 
 Re: 1000 городов, одностороннее движение.
Сообщение30.08.2014, 12:29 
Я подумал, что может возникнуть ситуация, когда город $k+1$ соединен со всеми остальными городами так, что все дороги исходят из $k$. Вот картинка примерная.
Изображение
1) При этом, если из $k+1$ города выехать в первый, то можно объехать все города (побывав в каждом только один раз), односторонность соблюдется!
2) Если будет ситуация, когда все дороги из городов $1,2,..,k$ ведут в город $k+1$, то можно объехать все города (побывав в каждом только один раз, выехав из 1 города во второй), односторонность соблюдется!
Но, например, вот в такой ситуации -- движение не будет односторонним.
Изображение
Мне кажется, что третьего варианта -- нет, потому как движение не будет иначе односторонним. То есть либо все города соединены дорогой из $k+1$, либо все города соеденены дорогой в $k+1$. В обоих случаях можно объехать все города, побывав в каждом ровно один раз. Значит по индукции доказали. Верно?

 
 
 [ Сообщений: 17 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group