[阅读: 319] 2004-07-02 02:30:24
灌水问题:
有一张长桌,N个人坐成一排。
桌上有N+1个杯子。每两人之间有1个,另外两头也各有一个。也就是说,从左到右,依次是:
杯子、人、杯子、人、。。。杯子、人、杯子。
N+1个杯子中,有K个杯子是满的,其他是空的。
规则1:每个人都可以做这样一个动作,就是当他左右两个杯子为一空一满的时候,他可以把满杯里的水倒进空杯里。如果两个都是空的,或两个都是满的,则此人不准行动。
规则2:任两个人不能同时动。也就是说,等一个人倒完后,另一个人才能倒。
规则3:当一个人倒过之后,除非他隔壁的人也倒过,否则他不能再倒一次。也就是说,某人把左手的水倒到右手后,如果相邻的两人都不动,此人不能再把右手的水倒回左手。(如果是最边上的一人,他的邻居只有一人。)如果他的某个邻居在他第一次动作之后某个时刻也倒过了,这样的话他才能在今后再倒。
问:不管初始时刻K个满杯的分布情况如何,所有的人最多一共倒几次?
DISSENT IS THE HIGHEST FORM OF PATRIOTISM !
--Thomas Jefferson