Forgot password?
 快速注册
Search
View: 1403|Reply: 3

[组合] 求证存在一直线与所有多边形都相交

[Copy link]

413

Threads

1558

Posts

110K

Credits

Credits
11498

Show all posts

abababa Post time 2014-10-1 20:35 |Read mode
平面上给定有限个多边形,其中任意两个多边形都有公共点,求证存在一直线与所有多边形都相交

413

Threads

1558

Posts

110K

Credits

Credits
11498

Show all posts

 Author| abababa Post time 2014-10-18 19:28
发一位网友的证明,大致思路看懂了,就是中间觉得有点繁琐:
建立坐标系,设$f$将多边形$C_i$上的点投影到横轴,于是$f(C_i)$为线段$L_i$
不妨设当$i < j$时$L_i$的左端点小于$L_j$的左端点
设$[x_1,x_2) = T_1 = L_1-L_2, [x_2,x_3] = T_2 = L_1 \cap L_2, (x_3,x_4] = T_3 = L_2-L_1$,显然$T_1, T_2, T_3$两两不相交
假设$L_3 \cap T_2 = \varnothing$,由于$L_3 \cap L_1 \neq \varnothing$,所以$\exists y_1 \in L_3 \cap T_1, x_1 \le y_1 < x_2$,同理有$\exists y_2 \in L_3 \cap T_3, x_3 < y_2 \le x_4$
而$L_3$连续,所以$[y_1, y_2]$连通,则由于$y_1 < x_2 < x_3 < y_2$,所以$[y_1, y_2]$覆盖$T_2$,这与$L_3 \cap T_2 = \varnothing$矛盾
所以$\exists f(P) \in L_3 \cap T_2 = L_1 \cap L_2 \cap L_3$,同理有$\exists f(P) \in \displaystyle\bigcap_{i=1}^{n} L_i$,于是过点$P$的直线与所有多边形都相交

413

Threads

1558

Posts

110K

Credits

Credits
11498

Show all posts

 Author| abababa Post time 2014-10-20 09:01
借助网友的思路,我试着简化一下,大家看看有没有什么错误:
假设所有投影线段没有公共点,那么存在两条投影线段没有公共点,这样就存在两个多边形没有公共点,与已知矛盾
所以假设错误,即所有投影线段至少有一个公共点,这样过这个点作y轴的平行线,这条直线就和所有多边形都相交

443

Threads

1519

Posts

110K

Credits

Credits
11660

Show all posts

realnumber Post time 2014-10-21 00:06
意思看明白了,这类问题的推理怎样算严谨,还是不清楚。

手机版|悠闲数学娱乐论坛(第3版)

2025-3-5 09:49 GMT+8

Powered by Discuz!

× Quick Reply To Top Return to the list