ACM通信

最后一个字节

保持平衡

丹尼斯·沙沙村
ACM通信，2021年1月，第64卷第1期，第128页
10.1145 / 3434645
评论

两名选手，每个人都有一系列的重量，坐在一块3公斤重的木板前，在−1和+1处有两个支撑。每个玩家都想通过将他们放在积分标记上来摆脱他或她的权重，每个积分标记最多一个权重。例如，玩家A可能不会把一个权重放在A或玩家B的权重之上。此外，任何玩家都不允许将权重设置为−1、0或+1。

在一个回合中，玩家必须在木板上放置至少一个重物，但可以在木板上放置多个重物，如果它们是连续的整数标记。每个选手的目标是第一个把他或她的所有重量都放好，而不导致木板倾斜(通过在右侧支架上有一个严格的负扭矩或在左侧支架上有一个严格的正扭矩)。

热身:假设所有重量都是1公斤，每个选手有6个重量。假设每个玩家总是在每一步中放置尽可能多的重量(一种“贪婪”策略)。哪位选手会赢?

热身的解决方案:第一个玩家可以将权重设置为+2和+3。因此，左支架上的扭矩为−(3*1 + 1*3 + 1*4)，右支架上的扭矩为0。参与人2可以将权重设为−2，−3，−4，−5。现在右支架上的扭矩为(1*6 + 1*5 + 1*4 + 1*3 + 3*1)-(1*1 + 1*2)= 18。左边支架上的扭矩现在是0。因此，第一个玩家可以在+4，+5，+6，+7处添加权重并获胜。

如果我们有6个1千克的重量，每个都是贪心的，那么第一个玩家赢。

问题:如果每个玩家都有7个1千克的重量，并且每个玩家都是贪婪的，那么哪一个玩家会赢?

解决方案:每个玩家都像以前一样玩。当第一个玩家添加了+4，+5，+6，+7的权重后，左侧支架上的扭矩为-(5 +6 +7 + 8)= - 26，第二个玩家可以将他或她的最后一个权重设置为- 6并获胜。

数字六斤木板。“我怎样才能第一个把所有重量都放在木板上而不使木板倾斜呢?”

问题:如果木板更重，上面的情况会改变吗?

解决方案:是的，举个例子，如果木板重得多，那么第一个玩家就可以把他所有的重量都放在一边。

在非贪婪玩法中，每个玩家在他或她的回合中必须将至少一个重量放在木板上的某处。如果有多个权重，则它们必须是连续的。

在接下来的新贵中，假设与之前相同的规则:木板重3公斤，重量只能放在整体制造商上，不能放在另一个重量上。

Upstart 1:如果先动的玩家可以选择每个玩家开始时的10个积分重量，且每个重量至少为1公斤，并且所有的重量都是不同的，那么是否有办法保证先动的玩家能够获胜呢?

Upstart 2:一个玩家是选择者，他得到一个n必须选择准确n不同的重量，每个重量必须是公斤的整数，≥1。非选择者决定是先走还是后走。两者都必须贪婪地玩。的值n选择者能保证获胜吗?

Upstart 3:就像在Upstart 2中，选择器，给定一个n，必须正确选择n不同的重量，每个重量必须是公斤≥1的整数。选择者决定是先走还是后走，但必须贪婪地玩。不选择的人不必贪玩。的值n选择者能保证获胜吗?

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.

---

没有发现记录