Basic definition:
内固集 外固集 核
BZOJ 2275
Fibonacci game.
Theorem The game with initial state of Fibonacci number will get failed.
Proof. By induction.
(i) Obv $ i = 2 $ get failed. Checked.
(ii) Assume $ i \le k $ valid. Let $ i = k + 1 $. Denote $ x $ as the first amount, $ y $ as the second.
We have $ x \ge \frac{1}{3} f_{k-1}, y \le \frac{2}{3} f_{k-1} \le \frac{1}{2} f_k $. The second one get the last stone, which means the first failed. QED.
Theorem(Zeckendorf) $\forall n \in \mathbb{N}\_+ $, n can be represented by a discontiniousness sequence of Finobaccis.
Proof: By induction.
(i) $ n = 2, 3 $, obv.
(ii) Assume $n = 1..m-1$ valid. Consider the case of $ n = m $.
(a) $ m \in \mathcal{F} $, valid.
(b) $ m \not\in \mathcal{F} $, let $ F_{n_1} < m < F_{n_1+1} $, we have $ m' = m - F_{n_1} < F_{n_1-1} $, by assumption, follow the previous we can define such $ n_i $ s. Since $ n_2 < n_1-1 $, we get the conclusion. QED
By the 2 thms above, we know the previous player who take $ \min F_n $ at the very first time will win the game.
Code (8632 kb 4 ms)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
using namespace std;
template<class T> void read(T& x)
{
T p = 1, n = 0; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') p = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){n = n * 10 + ch - '0'; ch = getchar();}
x = p * n;
}
const int maxn = 1e6;
long long f[maxn];
int main()
{
long long n; read(n);
f[0] = 1, f[1] = 2;
int cur;
for(cur = 2; f[cur - 1] <= n; cur++) f[cur] = f[cur - 2] + f[cur - 1];
cur--;
while(n)
{
while(f[cur] > n) cur--;
if(f[cur] == n)
{
printf("%lld\n", f[cur]);
return 0;
}
n -= f[cur];
}
return 0;
}
HDU 2516
Code(1540K,0)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
using namespace std;
template<class T> void read(T& x)
{
T p = 1, n = 0; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') p = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){n = n * 10 + ch - '0'; ch = getchar();}
x = p * n;
}
const long long maxn = 1e6, maxm = 1LL << 31;
long long f[maxn];
set<long long> S;
int main()
{
long long n;
f[0] = 0, f[1] = 1; S.insert(0); S.insert(1);
for(int cur = 2; f[cur - 1] <= maxm; cur++)
f[cur] = f[cur - 2] + f[cur - 1], S.insert(f[cur]);
while(read(n), n)
puts(S.count(n) ? "Second win" : "First win");
return 0;
}
Wythoff Game
Theorem(Beatty) Let $ \frac{1}{\alpha} + \frac{1}{\beta} = 1, \alpha, \beta \text{~irrational}, a_n = \lfloor \alpha n \rfloor, b_n = \lfloor \beta n \rfloor $, then we have
(1) $ {a_n}, {b_n} $ is increasing;
(2) $ {a_n} + {b_n} = \mathbb{N_+} $.
Proof. (1) It's easy to find out $ \alpha,\beta > 1 $, which implies the increasing.
(2) Assume that $ a_p \le k, a_{p+1} > k, k \in \mathbb{N}_+ $. We have
$$
\begin{align}
\alpha p < k+1 \\\\
\alpha(p+1)>k+1
\end{align}
\Rightarrow p = \lfloor \frac{k+1}{\alpha} \rfloor \\\\
\Rightarrow S = \frac{k+1}{\alpha} + \frac{k+1}{\beta} \\\\
\Rightarrow k-1<S<k+1 \\\\
\Rightarrow S = k
$$
which means the previous k numbers get the first k numbers in natural number set.
Q.E.D.
By definition of the game, we can easily figure out that each odd situation (shown by a pair (a, b)) satisfies the following proposition: (Assume the first element of the pair is less than the second)
(i) We have $ (a_i, a_i + k) $ for the $ k $-th odd;
(ii) a_i is the minimum excluded integer from the previous pairs;
(iii) The first non-trial odd is $ (1,2) $.
By Beatty's Theorem, we let $ \beta - \alpha = 1 $, then we know the sequence $ a, b $ is what we find to describe the odds of the game. In general, each odd has a form as $ (\lfloor \frac{1+\sqrt{5}}{2} n \rfloor, \lfloor \frac{1+\sqrt{5}}{2} n + n \rfloor) $, where $ n $ is an integer meaning the order.