论 First Principle
前几天和 hls bibi 了一下。hls 推荐了 这个视频 给我。我是以一个批判的角度看视频的，就像我之前 review paper 一样，先把屁股坐住了再来找论据，所以大部分观点都是 biased 的，可能就是在 nitpicking。
The Optimal Order to Purchase Vampire Survivors Power Ups
The cost for Power Ups has changed since version 0.7, so this post is no longer applicable.
\(\newcommand{\eps}{\varepsilon} \newcommand{\R}{\mathbb{R}}\) Vampire Survivors is a game released in early access near the end of 2021. It received 110k recommendations in one month, which is pretty amazing given its minimal aesthetics and seemingly low production costs. I also played it a lot back then, but I won't talk about its gameplay here. Instead, this post discusses the (old) Power Up mechanism and some of the math behind it.
The Power Up mechanism in Vampire Survivors is similar to Kingdom Rush's Upgrades, where you spend the gold earned during gameplay to make permanent gains (e.g., increase move speed by x%). As per the notes in Fandom, the cost for a Power Up is defined as: \[ Price = \text{InitialPrice} \cdot (1 + \text{Bought}) \cdot \left(1 + \frac{\text{TotalBought}}{10} \right), \] where \(\text{InitialPrice}\) is the initial price of the Power Up, \(\text{Bought}\) is the number of purchased ranks for this Power Up, and \(\text{TotalBought}\) is the total number of purchased ranks among all Power Ups. What's interesting is that the order in which you buy Power Ups actually matters!
Intuitively, we should purchase expensive Power Ups first. For example, IGN recommends maxing out Power Ups with the highest initial costs first. However, this is not optimal. Suppose we have two Power Ups, A and B. A has 5 ranks with an initial price of 1, while B has only 1 rank with an initial price of 2. If we max out A first, the total price is: \[ 1 \times 1 + 1.1 \times 2 + 1.2 \times 3 + 1.3 \times 4 + 1.4 \times 5 + 1.5 \times 2 = 22, \] and if we max out B first, the total price is: \[ 1 \times 2 + 1.1 \times 1 + 1.2 \times 2 + 1.3 \times 3 + 1.4 \times 4 + 1.5 \times 5 = 22.5. \]
So, here is our central topic today:
What is the optimal order for buying all Power Ups?
Lake Tahoe 游记
几个星期前，我和朋友们去了趟湾区的后花园 Lake Tahoe，这里就随便写点东西记录一下。由于时间比较短，我们只过了一个周末，所以显得这篇文章尤为流水帐 23333
Magic Numbers
很多文件格式都是以一个 Magic number 开始，例如 Java 编译后的字节码文件就是以 CAFEBABE 开头。Wikipedia 上还有一个 表，里面放了很多好玩的 magic number，例如 DEADBEEF （还有个音乐播放器叫这个名字）和 FEE1DEAD （linux 的 reboot syscall 中用到）。于是我就心血来潮，能不能整出类似的看起来像英文词组的 magic numbers 。
平铺矩形
试证明：如果一个大矩形能被有限个小矩形（大小不一定相同）平铺，且小矩形至少一条边为整数，则大矩形至少有一条变为整数。
解答
注意到积分 \[\int_{a}^b e^{2 \pi i x} \mathrm{d} x = e^{2 \pi i a} \left(e^{2 \pi i (b - a)} - 1 \right)\] 为 0 当且仅当 \(b - a \in \mathbb{Z}\)。对于平面上一个矩形区域 \(R\)，我们考虑如下积分：\[I(R) = \iint_R e^{2\pi i (x + y)} \mathrm{d} x \mathrm{d} y,\] 这个积分值为 0 当且仅当 \(R\) 至少有一边长为整数。令 \(R^*\) 为大矩形，\(R_{1, \dots, n}\) 为小矩形，则有 \[I(R^*) = \sum_{i} I(R_i) = 0,\] 故 \(R^*\) 至少有一条边长为整数。
事实上这个题还有很多种证明方法（14 种！），但我最喜欢的还是这个基于积分的证明。
参考资料：
- Fourteen Proofs of a Result About Tiling a Rectangle, Stan Wagon.
- Simple Proofs of a Rectangle Tiling Theorem
- Mathematical Puzzles, Revised Edition, Chapter 24, Integral Rectangles
夏威夷旅游小记
今年上半年，ydl 找到我，说他和 maggie 订婚了，诚邀我去 Hawaii 参加婚礼。这我怎么能不参加呢？况且我还没去过 Hawaii，自然应该趁这个机会小小旅游一下。这里就随手记一下流水帐。这次旅游之后，终于知道 Hawaii, O'ahu, Waikiki, Honolulu 之间的关系了……
后来发现一个有趣的 trivia：夏威夷的 state fish 叫做 Humuhumunukunukuapua'a，虽然看起来很长，但是读起来非常有节奏感 23333
IMO 2024 P1 & P5
听说今年这两道题比较简单，我就来蹭蹭热度了。 P1 是一个不太难的题，但是我很可能把它想复杂了；P5 是一个非常巧妙的 brainteaser 。
P1
求所有实数 \(\alpha\) 满足：对任意正整数 \(n\)，整数 \(\sum\limits_{i=1}^n \lfloor i \alpha \rfloor\) 均为 \(n\) 的倍数。
解答
令 \(S\) 表示所有满足要求的 \(\alpha\) 构成的集合。先来个小观察：如果 \(\alpha \in S\)，那么 \(2 + \alpha \in S\)：对于任何 \(n \in \mathbb{N}^+\)，有 \[\sum_{i=1}^n \lfloor i (\alpha + 2) \rfloor = \sum_{i=1}^n \left( \lfloor i \alpha \rfloor + 2i \right) = \sum_{i=1}^n \lfloor i \alpha \rfloor + n (n + 1)\]
于是我们就只需要研究 \([0, 2)\) 里的 \(\alpha\) 即可。
- 显然有 \(0 \in S\);
- 如果 \(0 < \alpha < 1\)，考虑 \(n = \lceil \alpha^{-1} \rceil \geq 2\)，有 \(\sum\limits_{i=1}^n \lfloor i \alpha \rfloor = 1\)，明显不满足要求；
- 显然有 \(1 \not\in S\)：令 \(n = 2\) 即可。
- 如果 \(1 < \alpha < 2\):
- 如果 \(\alpha \not\in \mathbb{Q}\)，对于任何 \(n \in \mathbb{N}^+\) 有 \(\sum\limits_{i=1}^n \lfloor i (2 - \alpha) \rfloor = \sum\limits_{i=1}^n (2i - 1 - \lfloor i \alpha \rfloor)\) ，故 \(2-\alpha \in S\)，又有 \(0 < 2 - \alpha < 1\)，矛盾。
- 如果 \(\alpha \in \mathbb{Q}\)，不妨令 \(\alpha = p / q\) 且 \(gcd(p, q) = 1, q > 1\)。有 \[\sum_{i=1}^{q-1} \left\lfloor i \frac{p}{q} \right \rfloor = \frac{1}{2} \sum_{i=1}^{q-1} \left( \left\lfloor i \frac{p}{q} \right \rfloor + \left\lfloor (q - i) \frac{p}{q} \right \rfloor \right) = \frac{p - 1}{2} (q - 1) \equiv 0 \pmod {q - 1}. \] 可知 \(p\) 为奇数。又考虑 \[\sum_{i=1}^q \left\lfloor i \frac{p}{q} \right \rfloor = p + \frac{1}{2} \sum_{i=1}^q \left\lfloor i \frac{p}{q} \right \rfloor = p + \frac{p - 1}{2} (q - 1) \equiv 0 \pmod{q}. \] 可得 \[\frac{p + 1}{2} \equiv 0 \pmod{q},\] 而这是不可能的，因为 \(0 < \frac{p + 1}{2} < q\).
综上所述，\([0, 2) \cap S = \{0\}\)，故 \(S = \{2k: k \in \mathbb{Z}\}\).
（这个对 \(\alpha \in \mathbb{Q}\) 的讨论好丑好想优化掉……）
P5
憨豆特工在一个 2024 行 2023 列的方格表上做游戏。方格表中恰有 2022 个方格各藏有一个坏人。初始时，憨豆不知道坏人的位置，但是他知道除了第一行和最后一行之外，每行恰有一个坏人，且每列至多有一个坏人。
憨豆想从第一行移动到最后一行，并进行若干轮尝试. 在每一轮尝试中，憨豆可以在第一行中任意选取一个方格出发并不断移动，他每次可以移动到与当前所在方格有公共边的方格内。（他允许移动到之前已经到达过的方格。）若憨豆移动到一个有坏人的方格，则此轮尝试结束，并且他被传送回第一行开始新的一轮尝试。坏人在整个游戏过程中不移动，并且憨豆可以记住每个他经过的方格内是否有坏人。若憨豆到达最后一行的任意一个方格，则游戏结束。
求最小的正整数 \(n\)，使得不论坏人的位置如何分布，憨豆总有策略可以确保他能够经过不超过 \(n\) 轮尝试到达最后一行。
解答
以下给出一个 \(n = 3\) 的构造。所有的图里蓝色为坏人，黄色表示可行路径。
我们先确定第二行的坏人在哪里。这一步直接扫就好了。有两种情况：
- Case 1：坏人不在第一列或最后一列。如图所示，A 点和 B 点同行，所以至多有一个坏人。不妨设 B 点没坏人，按照黄色路径走即可。
![Case 1]()
- Case 2：坏人在第一列或最后一列。不妨设坏人在第一列，那我们便从上到下依次遍历下图的所有绿色方块，遇到第一个坏人就停止。
![Case 2]()
- Case 2-1：我们没有找到任何一个坏人，那么我们可以直接走最后一列即可；
- Case 2-2：我们找到了一个坏人，那么按照下面的黄色路径走即可：
![Case 2-2]()
A 点左上方的点没有坏人是因为 A 点是我们从上往下扫找到的第一个坏人。
A 点左上方的点没有坏人是因为 A 点是我们从上往下扫找到的第一个坏人。至于 \(n\) 为啥不能小于 3：我们就考虑一个 adversarial 的放坏人的方式，
- 第一次探索时我把坏人放在你探索的第一个方块上（在第二行）；
- 第二次探索时我把坏人放在你探索的第一个位于第三行的方块上，这个方块一定和我第一次放坏人的方块不在同一列上，因为你只能从第二行的非坏人方格到第三行。
SIGYAO30 2024 @ Chicago
又是一年 SIGYAO30。今年 SIGYAO30 在 Chicago，一来是因为之前美东美西都举办过 SIGYAO30 了，二来去年商定举办地点的时候，刚好 Chicago 有三个人，于是我们就决定放在 Chicago 了。事实上，我对芝加哥 downtown 印象挺好的，现代的城市，干净的街道，便捷的生活，低廉的物价，丰富的娱乐，多样的美食，就是冬天有点冷，南边不安全……
七年前才毕业，到现在居然已经毕业七年了。上次在芝加哥还是上次。半年不见，如隔六月。这次来芝加哥体验了好多游客项目，我在芝加哥住了一年半，但凡我稍微出门逛逛，也不至于一点也没逛。
2024年新高考 1 卷数学最后一题
现在不是刚好在高考嘛，我也来看了一下，看有没有新东西……
妙题一道（圆覆盖）
这是一道来自王格斯的妙题，有一个 10s 内能说出来的解法。
一个能被 25 个半径为 1 的大圆覆盖的长方形一定能被 100 个直径为 1 的小圆覆盖吗？