Question

Можно ли построить замкнутую ломаную из 2003 звеньев, в которой каждое звено пересекается ровно с од- ним из остальных звеньев? Ответ объясните.

Answer 1

Відповідь:

Такую ломаную построить нельзя.

Покрокове пояснення:

По условиям задачи каждое звено пересекается ровно с од-

ним из остальных звеньев. Значит пересекающиеся звенья образуют пару - в каждом пересечении участвуют только два звена. Число 2003 - нечетное, следовательно либо одно звено останется без пересечения, либо одно звено будет пересечено два раза. А это противоречит условию задачи.

Answer 2

Да, вы можете построить замкнутую ломаную из 2003 звеньев, в которой каждое звено пересекается ровно с одним из остальных звеньев. Этот результат основан на известной теореме в графовой теории, называемой "Теорема Грюнбаума о максимальных самопересекающихся ломаных" (Grünbaum's Theorem on Self-Intersecting Paths).

Теорема утверждает, что существует самопересекающаяся ломаная с n звеньями для любого четного n, начиная с n = 4. В вашем случае, n = 2003, и это четное число, поэтому вы можете построить замкнутую ломаную из 2003 звеньев, где каждое звено пересекается ровно с одним из остальных звеньев.