浙江省初中数学竞赛复赛最后一题 大致意思:
有7个人,两两比赛一次,只有胜负,没有平局,如果A胜B,B胜C,C胜A,那么称ABC是一个"圈",问最多有几个"圈",并证明.
-------------------------------
设这七个人为平面上七个点,这些点每两个点用有向线段相连,这7个点为P1,P2,...P7,确定的三角形为C(7,3)=35,设Pi为始点的有向线段为xi(即Pi获胜场次),0<=xi<=6,在一个三角形中不能形成圈的有且仅1个点是两边的始点,,所以,以Pi为顶点之一且不能形成圈的有C(xi,2),(规定C(1,2)=C(0,2)=0),所以不能形成圈的三角形的总数为∑C(xi,2)累加到7,因此圈有C(7,3)-∑C(xi,2),只须求∑C(xi,2)的最小值,首先∑xi=C(7,2)=21,所以∑C(xi,2)=∑xi(xi-1)/2=0.5∑xi^2-21/2,因非负整数xi不超过6,所以∑xi^2有最小值,设1≤i,j ≤7(i≠j),使得xi-xj≥2 ,可记xi'=xi-1,xj'=xj+1,显然有xi>xi'≥xj'>xj,则xi^2+xj^2-(xi'^2+xj'^2)=2(xi-xj-1)>0,又xi是正整数,对于所有1≤i,j ≤7,只有当|xi-xj|=0或1时才取到最小值即当{xi}={3,3,3,3,3,3,3}时取到最小值
最后算得最小值为∑C(xi,2)=3^2*7/2-21/2=21
所以最多有C(7,3)-21=14个圈