组合极值趣题

2023年4月30日，第五届OUFC在广州举办。其中有一项活动是毛毛火车。有100只毛毛只有一条红尾巴，另外100只毛毛只有一条蓝尾巴。这200只毛毛按照如下方式围成一个圈：每只毛毛都牵着它前面的那只毛毛的尾巴，同时被它后面的那只毛毛牵着尾巴。规定：对每只毛毛而言，如果它牵的尾巴与它自己的尾巴颜色相同，则自己得1分，反之自己得-1分。求这200只毛毛总得分的最大值与最小值的差。 解析： 可以发现，顺时针还是逆时针方向牵尾巴，不影响总得分。 要想得分尽可能高，相同颜色尾巴的毛毛应该尽可能相邻；要想得分尽可能低，不同颜色尾巴的毛毛应该尽可能相邻。 如图1，当红、蓝尾巴的毛毛交替排列时，任两只相邻的毛毛尾巴都不同色，此时总得分最低，为（-1）×200=-200分。 如图2，当100只红尾巴毛毛排在一起，100只蓝尾巴毛毛排在一起时，红、蓝尾巴毛毛各有100-1=99只毛毛牵着与自己尾巴同色的尾巴，恰有红、蓝尾巴各一只毛毛牵着与自己尾巴不同色的尾巴。此时总得分最高，为2×99-2=196分。 所以总得分最大值与最小值的差是396分。