1. 问题

传送门 (opens new window)

魔术师实现和助手商量好策略。他们拿出 124 张不同的牌，请观众背着魔术师随便挑 5 张交给助手；助手观看这 5 张牌，从中挑选一张还给观众，再把剩下的 4 张牌按事先设计的策略排好顺序，交给魔术师看。要求魔术师能从拿到手的 4 张牌及其顺序推理出助手交还给观众的牌。请给出一个助手选牌和排序的策略。

2. 初步思考

由于 124 张牌不重复，除掉已知的 4 张牌，隐藏牌只有 120 种可能。

魔术师可以从 4 张牌的顺序种获得信息，一共 24 个排列。在这个基础上，魔术师已经有 $\frac{1}{5}$ 的概率猜对了。

因此这个问题的关键在于，助手如何让魔术师从 5 个选项中做出正确选择。

3. 解答

这个问题的答主已经给出了方案，但是有个细节并没有讲对，我花了很多时间才明白。

假设助手拿到的数排序后为 $a_0,a_1,a_2,a_3,a_4$。令 $i$ 为 $(a_0+a_1+a_2+a_3+a_4)$ 对 5 取模，助手只要将 $a_i$ 拿出来，并利用剩下 4 张牌的全排列的信息将 $\lfloor\dfrac{a_i-i-1}{5}\rfloor$ 表示出来。

假设魔术师看到了 $b_0,b_1,b_2,b_3$，只要计算 $-(b_0+b_1+b_2+b_3)$，得到的数与 小于未知数且不在 4 张牌里出现过的正整数个数 + 1 同余。所以魔术师应该先结合全排列的信息将 小于未知数且不在 4 张牌里出现过的正整数个数 + 1 求出来，再结合 4 张牌计算未知数。

在这个问题中，因为 124 是 $C_m^5\le A_m^4$ 的 m 的最大正整数解，因此如果问题中 124 改为更大的数字，理论上是无解的。

4. 代码实现

助手是 Alice，魔术师是 Bob。

先读入 n，表示助手一开始拿到 n 张牌（原问题 n = 5），再读入 n 个数字，要求 $1 \le a_i \le (n! + n - 1), a_i \neq a_j$。

#include <bits/stdc++.h>
using namespace std;
vector<int> Alice(vector<int> a) { // n cards => (n - 1) cards
    size_t n = a.size();
    sort(a.begin(), a.end());
    int pos = accumulate(a.begin(), a.end(), 0) % n;
    size_t offset = (a[pos] - pos - 1) / n;
    a.erase(a.begin() + pos);
    for (size_t i = 0; i < offset; i++) {
        next_permutation(a.begin(), a.end());
    }
    return a;
}
int Bob(vector<int> a) { // (n - 1) cards => unknown card
    size_t n = a.size() + 1;
    int ans = n - accumulate(a.begin(), a.end(), 0) % n;
    while (prev_permutation(a.begin(), a.end())) ans += n;
    sort(a.begin(), a.end());
    for (size_t i = 0; i + 1 < n; i++) if (ans >= a[i]) ans++;
    return ans;
}
signed main() {
    size_t n; cin >> n;
    vector<int> a(n);
    for (size_t i = 0; i < a.size(); i++)
        cin >> a[i]; // 1 <= a[i] <= (n! + n - 1), a[i] != a[j]
    vector<int> b = Alice(a);
    for (size_t i = 0; i < b.size(); i++)
        cout << b[i] << " \n"[i + 1 == b.size()];
    cout << Bob(b) << endl;
    return 0;
}