求大神...!!!

哪里的竞赛题啊？你怎么不问晋之？

我觉得你应该到数学竞赛吧去问…这里的人都比较弱…

其实没人回不是因为吧友实力弱...如果楼主一题一题问，恐怕效果大不一样

内容多

第四题，
考虑如下的特殊情形，
如下图，把200个人分成66个3-圈，1个2-圈，

那么每一个圈中至多有有一个人被选为代表，
所以K≤66+1=67【然后我还在想怎么证明（或者推翻）K≥67】

终于证出来了，
分别用v[1],v[2],...,v[200]表示这200名教师，
若第i名教师给第j名教师发了短信，则引一条有向边v[i]→v[j]，
由此构成了有向图G，且每一个点的出度均为1，取消所有边的方向，得到无向图H，
先给出如下三个引理，
引理一：对于图H中的任一连通子图T，若|V|=k，则其边数|E|=k.
引理一是显然的，因为图G中每个点的出度均为1，
所以对图T，必可以作一个V(T)→E(T)的一一对应，从而|E|=|V|=k.
引理二：若图T中存在一个圈，则这个圈在图T取消方向前的有向图T'中是一个有向圈.
引理二的证明：
若结论不成立，则对于T上的这个圈，存在顶点v[i],v[j],v[k]，
在图T'中，从v[i]出发引出了两条有向边v[i]→v[j]，v[i]→v[k]，
这与有向图G中每一点的出度均为1相矛盾，所以结论成立.
引理三：有向图T'中至多存在一个有向圈.
引理三的证明：
若结论不成立，
如果两个有向圈相交，那么相交处的顶点出度必大于1，
如果两个有向圈不交，则存在T中的路线P-v[i]-...-v[j]-Q连接P,Q两个圈，
在图T'中，由于每个有向圈上的点的出度均为1，
故必定是v[i]→P，v[j]→Q，
这表明在路线P-v[i]-...-v[j]-Q必存在某个顶点出度大于1，矛盾！
所以结论成立.

将有向图G分解为若干个有向连通子图，
再考虑每一个连通子图中的顶点数，
以及归纳证明的结论，可知K[min]≥67，
结合12L的结论，可知K[min]=67.

膜拜q神

第四题。。。

我和我的小伙伴