一道组合趣题
自招级里的难题，大家看看什么思路网页版简直没法看。。。 几年级的题目 这个是高中的题目啊。。。发在初中。。。 chaijinsergi 发表于 2023-9-14 14:16
这个是高中的题目啊。。。发在初中。。。
一个知名公众号的初中升高中自招模拟题里面的。 huhuyang2010 发表于 2023-09-14 17:32
一个知名公众号的初中升高中自招模拟题里面的。
这是今年北大强基校测的真题 50种，通过反证法证明胜场最多的是49，那么依次有49，48，......26,而且26只有一个，由对称性依次有0,.....,23,同样23只有一个，剩余的两个人胜场何为49只可能为24，25 还好吧，排序+分析，50种。 小奥有这样一道著名的问题
n（n大于2）支球队进行单循环比赛，没有平局，没有球队全胜，
求证：一定能找到3支队伍甲、乙、丙，满足甲胜乙、乙胜丙、丙胜甲.
简证：找到胜场最多（可以是最多之一）的球队作为乙，
乙没有全胜，选一支战胜乙的队伍作为甲，
那么乙战胜的球队中一定能找到一支战胜甲的，作为丙.
(否则乙战胜的球队，甲都胜了，甲至少比乙多胜一场，与假设矛盾）
回到原题
50支球队中如果存在三支队伍甲胜乙、乙胜丙、丙胜甲，
考虑甲对其余47支队伍的战绩，因为没有平局，可知 24场是平衡线，即其中一定有至少24支战胜甲或者有至少24支球队负于甲，
若有24支战胜甲，取这24支队伍和甲、乙、丙共27支队伍，则其中没有一支队伍全负；
若有24支负于甲，取这24支队伍和甲、乙、丙共27支队伍，则其中没有一支队伍全胜。
于是知道，在题目条件下，不存在三支球队甲胜乙、乙胜丙、丙胜甲，
由前文所述问题知，必有一支队伍全胜，
对其余49支球队而言，依然不存在三支球队甲胜乙、乙胜丙、丙胜甲，
在这49队的相互比赛中，必然有一队战胜其余48队，
依次类推，50支队伍必然恰好分别胜了0~49场，积分互不相同，有50种. 大家兴致挺高。
我也给一个解法。
设a是获胜最多的队，显然胜场不少于25（50*49/2/50>24)。如果有球队b赢a，任意挑选a赢过的25支球队，和ab一起构成27支球队，只有b全赢才能保证有1队全胜，进而b的胜场高于a,矛盾!所以a赢了其它所有球队。
去除a,类推第二胜场队的队赢48场，第三是47，直到26场。同理可以推出最少胜场为0，其次1，直到23场。而且49-26，0-23胜场有且只有1队。剩余胜场50*40/2-(49+48+…+26)-(1+2+…+23)=49,只能选24+25。所以0-49胜场各1队。
实际上，设ai为赢了i个胜场的队，易知当i>j时，ai赢aj，任选27个队，下标最大的赢26场，最小的全输！
weblinker 发表于 2023-09-18 16:54
小奥有这样一道著名的问题
n（n大于2）支球队进行单循环比赛，没有平局，没有球队全胜，
求证：一定能找到3支队伍甲、乙、丙，满足甲胜乙、乙胜丙、丙胜甲.
简证：找到胜场最多（可以是最多之一）的球队作为乙，
乙没有全胜，选一支战胜乙的队伍作为甲，
那么乙战胜的球队中一定能找到一支战胜甲的，作为丙.
(否则乙战胜的球队，甲都胜了，甲至少比乙多胜一场，与假设矛盾）
回到原题
50支球队中如果存在三支队伍甲胜乙、乙胜丙、丙胜甲，
考虑甲对其余47支队伍的战绩，因为没有平局，可知 24场是平衡线，即其中一定有至少24支战胜甲或者有至少24支球队负于甲，
若有24支战胜甲，取这24支队伍和甲、乙、丙共27支队伍，则其中没有一支队伍全负；
若有24支负于甲，取这24支队伍和甲、乙、丙共27支队伍，则其中没有一支队伍全胜。
于是知道，在题目条件下，不存在三支球队甲胜乙、乙胜丙、丙胜甲，
由前文所述问题知，必有一支队伍全胜，
对其余49支球队而言，依然不存在三支球队甲胜乙、乙胜丙、丙胜甲，
在这49队的相互比赛中，必然有一队战胜其余48队，
依次类推，50支队伍必然恰好分别胜了0~49场，积分互不相同，有50种.
以此类推有点问题，后面轮次按上面处理方式凑不足27队一组。 huhuyang2010 发表于 2023-09-18 19:24
以此类推有点问题，后面轮次按上面处理方式凑不足27队一组。
那就稍微修改一下，第一轮可找出胜场最多的( 49 胜）队 A 和 最少的（ 0 胜）队 B，第二轮剩 48 队 ，同样取 3 队加 23 队再加 1 支队 A 或 B（根据甲对剩余 45 队 胜负关系，胜多取 B，胜少取 A）凑满 27 队，可知有胜场最多 的 48 胜队和最少的 1 胜队，以后每轮均可同理凑足 27 队，直至最后一轮剩余 2 队分别为 25 胜和 24 胜。
页:
[1]