\begingroup

桌子上摆放着 50 张卡片，每张卡片只能看到最上面的一面。每张卡片上有两个数字，每面一个。数字范围从 1 到 100，每个数字只出现一次。

Vasya 必须选择任意数量的卡片并将其翻转，然后把现在最上面的 50 个数字相加。如果

  1. 他必须同时翻转所有他想翻转的牌吗？

  2. 他能一次翻一张牌吗？

注意：一张卡片最多可以翻转一次。

来源：1999年圣彼得堡市数学奥林匹克竞赛。

\endgroup


最佳答案
1

\begingroup

第（1）部分

Vasya 至少可以得到2525分。如果露出的牌的总和为 2525 或更大，Vasya 可以不翻转任何一张牌。如果露出的牌的总和小于 2525，所有牌的背面的总和将大于 2525（因为牌的总和为 (100)(101)/2 = 5050）。因此 Vasya 可以通过翻转每一张牌来得到大于 2525 的数字。

第（2）部分

2525似乎仍然是极限，因为很容易编造一个假设来干扰任何策略。例如，假设卡片正面显示数字 26-75（含）。这些数字加起来是 2525（（75）（76）/2 – （25）（26）/2 = 2850 – 325 = 2525）。在这种情况下，不可能想出一个一致的策略来翻转一张卡片，因为那张卡片上很可能有 1-24 的数字。事实上，任何不是全部或全部的翻转都有可能导致小于 2525 的数字。假设第一次翻转是 1，第二次翻转是 2，第三次翻转是 3，等等。尽管不太可能，但这是可能的，并且不能保证结果大于 2525。

\endgroup

5

  • \begingroup
    对于第一个问题，有什么证据证明他不能保证做得比 2525 更好？
    \endgroup


    – 

  • \begingroup
    第 2 部分证明了两种情况的上限。
    \endgroup


    – 

  • \begingroup
    @HemantAgarwal 第 2 部分确实证明了两种情况的上限；老实说，将它们合并到一个解释中是可能的，但我觉得将其与问题保持一致，并使用两部分答案会更好。
    \endgroup


    – 

  • \begingroup
    另一种思考方式是，一次翻转一张牌并不能保证获得一定的结果，因为我们必须假设翻转每张牌的最坏结果。随机翻转的最坏结果会使分数下降，然后需要翻转另一张牌。我们可以一次性翻转我们标记为“潜在翻转”的所有牌，因为在最坏的情况下，我们无论如何都会翻转每一张牌（否则它们甚至不是“潜在”翻转）。
    \endgroup


    – 

  • \begingroup
    @NuclearHoagie 这是我试图在第二部分的解决方案的结尾得到的，尽管你的表述方式更容易理解
    \endgroup


    –