AFAIK

Valar Morghulis

Posted on In Disqus: Word count in article: 1.3k Reading time ≈ 5 mins.

很多文件格式都是以一个 Magic number 开始，例如 Java 编译后的字节码文件就是以 CAFEBABE 开头。Wikipedia 上还有一个 表，里面放了很多好玩的 magic number，例如 DEADBEEF （还有个音乐播放器叫这个名字）和 FEE1DEAD （linux 的 reboot syscall 中用到）。于是我就心血来潮，能不能整出类似的看起来像英文词组的 magic numbers 。

首先我们要限定一下范围：

  • 字符串长度限制为恰好为 8；
  • 能被拆成一个或多个英文单词。由于英文单词也没有准确的定义，和之前一样，我这里采用 unix 自带的字典。
  • 字符集允许 0-9A-F 。这字符集有点小，但是我们可以整一些字符的 alias
    • O => o
    • I => 1
    • L => 1。由于 I 和 L 都映射到了 1，所以我限制这两个字母不能同时出现
    • ATE => 8
    • 或许可以允许 S => 5？
    • 或许可以允许 K => C？
    • 或许可以允许 G => 9？
  • 每个拆分的单词长度在 3-8 之间。

事实上，我们可以先看一下那些单词可以在这些规则下表示出来。

跑了之后发现里面这样 unix 自带字典 /usr/share/dict/words 太大，23w 个词，太多词我不认识了……为了解决这个问题我决定按照词频排序，于是我找到了 wordfreq 这个 repo。虽然他因为 AI generated content 污染决定不更新词频统计了，但是我们还是相信它吧。于是我们把词限定在这两个交集：可以去除一些人名地名、过去分词、专有名词，还可以按照词频排序。

我先看看有那些词替换之后直接就是 8 个字符。这种词总共只有 8 个：

ACC01ADE => accolade
F01DAB1E => foldable
CA11AB1E => callable
DEADFA11 => deadfall
CAB00D1E => caboodle
D011FACE => dollface
C0C0B010 => cocobolo
C0CC1D1A => coccidia

但是如果你允许 S => 5 的话，small list 都有一些了：

BA5EBA11 => baseball
DECEA5ED => deceased
A55E55ED => assessed
C01055A1 => colossal
5E1F1E55 => selfless
D15EA5ED => diseased
BA5E1E55 => baseless
5CAFF01D => scaffold

剩下要组词的话，由于限制 8 个字符，所以只能是一个 3-5 字符的词 + 一个 5-3 字符的词。这样的词总共只有 300 个左右，列表如下：

3-5 字符的词

 
A11      => all
D1D      => did
0FF      => off
01D      => old
FEE1     => feel
BAD      => bad
CA11     => call
FACE     => face
AB1E     => able
10CA1    => local
F00D     => food
1DEA     => idea
DEA1     => deal
1EAD     => lead
DEAD     => dead
ADDED    => added
C001     => cool
FA11     => fall
1ED      => led
B100D    => blood
ADD      => add
C0DE     => code
BED      => bed
D1E      => die
BA11     => ball
C01D     => cold
1CE      => ice
DAD      => dad
CE11     => cell
FE11     => fell
A1D      => aid
1EE      => lee
FEED     => feed
DEB8     => debate
B0B      => bob
BE11     => bell
10AD     => load
CAB1E    => cable
FED      => fed
FEE      => fee
C0A1     => coal
FACED    => faced
AC1D     => acid
1ABE1    => label
1AB      => lab
0DD      => odd
B1D      => bid
D0C      => doc
F100D    => flood
BEEF     => beef
F001     => fool
B01D     => bold
1EAF     => leaf
B1ADE    => blade
C01E     => cole
ACE      => ace
BABE     => babe
BEE      => bee
F01D     => fold
D011     => doll
F1ED     => fled
CA1      => cal
DEAF     => deaf
DA1E     => dale
CAB      => cab
C01      => col
10C8     => locate
B00      => boo
1AD      => lad
C0D      => cod
FADE     => fade
DEE      => dee
D0E      => doe
BA1D     => bald
1ACE     => lace
F1EE     => flee
BE11E    => belle
D1CE     => dice
DEED     => deed
C01A     => cola
FADED    => faded
B1EED    => bleed
CA1F     => calf
A1DE     => aide
A1E      => ale
DE11     => dell
F0CA1    => focal
A1EC     => alec
E1F      => elf
C0CA     => coca
C0C0A    => cocoa
BA1E     => bale
B10C     => bloc
AB1DE    => abide
BABA     => baba
BAE      => bae
C1AD     => clad
1EA      => lea
AD0BE    => adobe
A1A      => ala
F0E      => foe
C0C0     => coco
10AF     => loaf
1CED     => iced
BEAD     => bead
E11E     => elle
BE1      => bel
F1EA     => flea
B00B     => boob
CAD      => cad
F1FE     => fife
D0DD     => dodd
0B1      => obi
D0D      => dod
F00      => foo
A1BA     => alba
D01E     => dole
ABA      => aba
DAB      => dab
1AC      => lac
0DE      => ode
C00      => coo
10BE     => lobe
100      => loo
CE110    => cello
1ACED    => laced
DAE      => dae
F1DE     => fide
FAD      => fad
DA1      => dal
DEB      => deb
EE1      => eel
B1ED     => bled
10C0     => loco
AD0      => ado
B0A      => boa
FE1      => fei
DADE     => dade
FAB1E    => fable
C0E      => coe
1DE      => ide
AB0DE    => abode
BA1      => bal
A1F      => alf
BAC      => bac
F0B      => fob
DADA     => dada
0DA      => oda
A1FA     => alfa
B10B     => blob
A10E     => aloe
D10DE    => diode
B0D      => bod
CABA1    => cabal
C0B      => cob
EBB      => ebb
B0DE     => bode
B0B0     => bobo
DECA1    => decal
FECA1    => fecal

要组词的话其实挺简单的，因为这里面有足够的动词名词形容词：

  • 动词： 
    FEE1 => feel
    CA11 => call
    DEA1 => deal
    FA11 => fall
    FEED => feed
  • 名词 
    FACE => face
    FOOD => food
    1DEA => idea
    1CE  =>  ice
    BEEF => beef
  • 形容词 
    A11  =>  all
    01D  =>  old
    BAD  =>  bad
    C001 => cool
    DEAD => dead

如果只看 wordfreq small list 里的，那更少，只有 160 个。我自己稍微组了一些词：

FEE1BAAD => feel bad       这个其实不太可行，因为我用的 BAAD，也可以考虑 FEE15BAD
A10EFOOD => aloe food
DEB81DEA => debate idea
BADCAB1E => bad cable
ADD1ABE1 => add label
DEADF001 => dead fool      差一点变成了 deadpool
1EAFFA11 => leaf fall      让我想起了 e.e. cummings 的诗 l(a

如果我们不允许任何 alias，只用 A-F 来组词，也是能组出一些的：

DEADBEEF => dead beef    经典
FEEDBABE => feed babe    张嘴，啊～
FADEDDAD => faded dad    我去买个橘子？

我挑了一些词：

部分只包含 A-F 的词

 
BAD      => bad
FACE     => face
DEAD     => dead
ADDED    => added
ADD      => add
BED      => bed
DAD      => dad
FEED     => feed
DECADE   => decade
FED      => fed
FEE      => fee
FACED    => faced
BEEF     => beef
ACE      => ace
BABE     => babe
BEE      => bee
DEAF     => deaf
CAB      => cab
FADE     => fade
DEED     => deed
FADED    => faded
BEAD     => bead
FACADE   => facade
DAB      => dab
FAD      => fad
BEADED   => beaded
EBB      => ebb

可以看到长度为 5 的词很少，所以 3+5 和 5+3 这种搭配不好组词，只能 4+4 的组。

代码不长我就直接放这里了：

代码

 
import wordfreq
from pathlib import Path


def transform(x):
    result = x.upper()
    for c in x:
        if not c.isalpha():
            return None
    if "I" in result and "L" in result:
        return None

    # if result.endswith("ATE"):
    #     result = result[:-3] + "8"
    # result = result.replace("L", "1")
    # result = result.replace("O", "0")
    # result = result.replace("I", "1")
    # result = result.replace("S", "5")

    for c in result:
        if not c.isdigit() and c > "F":
            return None

    return result


dictionary = set(Path("/usr/share/dict/words").read_text().splitlines())


words = {}
for w in wordfreq.iter_wordlist("en", wordlist="small"):
    if w not in dictionary:
        continue
    w2 = transform(w)
    if w2 and w2 not in words and 3 <= len(w2) <= 8:
        words[w2] = w

for w2, w in words.items():
    print(f"{w:12} => {w2:12}")

Posted on In Disqus: Word count in article: 256 Reading time ≈ 1 mins.

试证明：如果一个大矩形能被有限个小矩形（大小不一定相同）平铺，且小矩形至少一条边为整数，则大矩形至少有一条变为整数。

解答

注意到积分 \[\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

Posted on In Disqus: Word count in article: 3.2k Reading time ≈ 12 mins.

今年上半年，ydl 找到我，说他和 maggie 订婚了，诚邀我去 Hawaii 参加婚礼。这我怎么能不参加呢？况且我还没去过 Hawaii，自然应该趁这个机会小小旅游一下。这里就随手记一下流水帐。这次旅游之后，终于知道 Hawaii, O'ahu, Waikiki, Honolulu 之间的关系了……

后来发现一个有趣的 trivia：夏威夷的 state fish 叫做 Humuhumunukunukuapua'a，虽然看起来很长，但是读起来非常有节奏感 23333

准备

出之前自然应该先订一下酒店。看了一下 ydl 他们推荐的酒店 Hyatt Regency Waikiki Beach，价格有点小贵，于是问了一下 ydl 还有谁来吗，结果发现 zw 也来，那我们又可以愉快的做室友了 23333

去之前肯定要稍微做一下攻略，刚好公司里有一个土生土长的 Waikiki 人，于是我就愉快的向他取了取经，拿到了一份《O'ahu 旅游宝典》可以直接抄答案了。

周六

由于我在 Hawaii 只待三天，都在 O'ahu 上，我就准备特种兵一下，早去晚会，maximize 在这里的时间。为此，我订了一个早上七点钟起飞的航班，早上五点钟就得挣扎着起床……飞机上也没睡好，整个脖子疼。这里给个建议：从美西去夏威夷最好坐飞机右侧，因为来的时候是从东向西飞，机场在岛南侧，所以坐在右侧能从天上看到岛的全貌。

到了夏威夷后，九点多，打个车到酒店大概十点多，然后震惊的发现，我打的这辆车下一个乘客就是 zhy 和 ljw……不过我当时脸盲真没认出来只看着眼熟哈哈哈哈哈囧……到了酒店后前台告诉我房间还没准备好，说好了会发短信告诉我，行李箱可以先寄存在酒店里面，妙啊，这样我就可以在 Waikiki 大走特走欣赏一下美丽的城市风景了。令人尴尬的是，就在楼下的 Bell Desk 我愣是找了半天才找到，而且还是找的侧门，出了门之后一看，BELL DESK 几个字母就大大方方的写在那里。脱下飞机上穿的长裤，换上一条短裤，Waikiki 我来啦！

出门就是 Waikiki Beach，但是里面人太多了（而且我也不会游泳）。拍了几张游客照我就想跑路了。接下来我就面临人生两大问题之一：中午吃什么？这个时候自然要问问万能的 xhs 啦～xhs 告诉我，这里可以吃日料，但是一个个都需要预订，很显然，我完全没有做准备。不要慌，我还有 wp 的 O'ahu 旅游宝典。wp 推荐的第一个餐馆叫做 Gina's BBQ。可以啊，让我体验一下什么才是正宗的 Hawaiian BBQ！我准备一路走过去，只要走四五十分钟就到了哦～于是打定主意，我就走了过去。这一路上都没啥树，在大太阳下走着晒死我了，路过了几家日料店，没有位置，路过了一个 Taco Bell，有啥好吃的，路过了一个 Mango Mango，都到夏威夷了怎么能吃这种大路货！最后终于走到了 Gina's BBQ，等等，为啥店名下面一个大大的 Korean BBQ？？？我再看了一眼菜单，没错，就是 Korean BBQ……不知道点啥就点了个 Gina's special，里面肉挺多的，但是问题是，我去哪里吃……这个店就一个门店，没有吃饭的地方啊……不慌，我看夏威夷这么多的公园，找个公园里的桌子不成问题！于是我又原路走回，这一路上都没啥树，在大太阳下走着晒死我了，路过了几家日料店，没有位置，路过了一个 Mango Mango，都到夏威夷了怎么能吃这种……啊真香！热的时候吃冷饮太香了！我路上试图招一个空地上的长桌来吃饭，但是问题是这些桌子全在草坪里，蚂蚁苍蝇来开会，我实在吃不下去，不能再现 SIGYAO30 '22 @ LA 的三和大神荣光了，直到——我有一次路过 Taco Bell。虽然我没买东西，但是 Taco Bell 有室外的水泥餐桌凳子，看起来不赶人，重点是，还有遮阳伞！我没有丝毫犹豫，直接坐在了 Taco Bell 的凳子上开始吃饭，吃饱喝足后旁边还有个垃圾桶，一气呵成！

之后我准备往 Diamond Head 那边走走看，拍几张游客照。走到一半收到短信说房间好了可以去 check in 了。那我自然应该往酒店走了。到酒店取出之前的行李后，ydl 就过来了，打了声招呼，我就去 check in 了，zw 到了之后一起去房间。

稍微修整了一下后我们就去下面玩，因为 zw 来的时候堵车了，原因就是有一个 festival 封路。既然来都来了，不如我们就去逛逛吧。这个 festival 叫做 Kanikapila Waikiki Festival，就在我们酒店旁边，但是去了之后有点大路货……所谓的 festival 就是一堆小贩在街边支个摊子，然后卖一些有的没的的东西。有些东西还稍微有点特色，例如自称 Hawaii 本地蜂蜜，但是有些东西就毫无特色了，例如烤鱿鱼，写着名字的竹子……

回到酒店后遇到了人生两大问题的第二个问题：晚上吃什么？经过 zw 一顿搜索，我们决定吃一家日式烧烤店，叫做 Aburiya Ibushi，打电话订了今天晚上最后一个位置。味道整体还可以，小菜里的 Cold Tofu 感觉很妙，上面淋的那层肉沫味道很好，wasyugyu sirloin steak 感觉也很好，不肥，入口即化，对比起来 beef flank 就差一些，不过看价格就看得出来 2333

晚上回到宾馆后在考虑明天搞些啥活动。我提议去去爬 Diamond Head 山，毕竟这个火山坑空中看起来超帅。但是这个 trail 需要预订，我们晚上预订的时候，7am-12pm 都已经被订完了，只剩下 6am-7am 或者 12pm 以后，但是 12pm 之后有点晚了，一来太热了我怕了，二来我们明天下午两点多需要在酒店集合坐车去婚礼现场。zw 表示我们可以早起特一特，于是我们就订了 6am-7am 这个时间。

周日

昨晚订的 trail，哭着也要爬完……但是 Diamond Head Summit Trail 这个还好，主要是比较短，往返就一个小时多一点。去的路上和司机 bibi 了一下，司机上来就问我们有没有预订，然后说一半以上的游客没有预订……但是机智如我们早已在昨天晚上订好了 23333 进了公园后就开始爬山。这个 trail 不长，单程只有 30-40min，一下子就爬完了。我发现我爬楼梯超级菜，稍微一爬膝盖就软了，不太对劲。虽然一开始是因为只有 6-7am 有时间我们才订的，但是爬的时候感觉就得这个时候爬，没有特别晒，温度也不高，天气很好，我估计九十点钟就太热了。不过我觉得山顶的景色一般吧，从山顶看 Waikiki 既没有一片高楼带来的现代气息，也没有纯粹自然的风景气息。

爬 Diamond Head Summit Trail 时看到的彩虹

爬了这个 trail 后我们就去打车回去了，补 wan 补 shou 觉 ji。中午吃的 Paia Fish Market，感觉还行，zw 说鱼非常新鲜但是我不知道什么新不新鲜……

下午说好的两点十五集合，我和 zw 就两点十分下去了，到了之后发现咋没人呢……有人和我打了个招呼，随便聊了两句但是我没认出来是谁，超级尴尬。到了两点半，人来齐了，我们开车前往 Kualoa Ranch，听说这还是拍侏罗纪公园的地方，但是我也没看过侏罗纪公园……车上我对着群里的名字一个一个找，终于想起了之前和我打招呼的是谁了……

之后婚礼正式开始了。这真是一个举办婚礼的好地方。我们在去婚礼现场的路上看到海上有一个小岛，感觉挺有意思的，查了一下叫做 China Man Hat Island。但是有意思的不只是这个，如果你从一个合适的角度去看婚礼花拱，你会发现这个岛恰好就在花拱中间，位置太妙了！

China Man Hat Island
花拱与 China Man Hat Island
Kualoa Ranch

婚礼进行的时候天有点阴，要是阳光再明媚一点就好了，不过另一方面想，我们就没那么晒了是吧哈哈哈。婚礼快要结束的时候，下起了点点细雨；婚礼刚刚结束的时候，这点点细雨变成了瓢泼大雨，也是天公给足了面子。我一开始仓促跑向避雨棚，忘记带小礼品了，这怎么能忘记呢！于是我像风一样跑了回去，又像风一样跑了回来。然而，这个时候我没有注意到，摄像师正拍着 ydl 保护 yfy 从容不迫地从婚礼现场来到避雨棚。希望将来他们回顾这份温馨的录像时，忽略掉一位一闪而过挡住了镜头的风一样的男子吧……

婚礼还配置了一个 photo booth，每次可以 1-3 个人一起拍摄三张照片。photo booth 还提供了很多塑料道具可以选择。我印象最深刻的一张是我、zw 还有 ydl 三个人的一张，ydl 坐中间，我和 zw 坐两边，zw 拿着手枪指着我，我拿着菜刀砍向 zw，ydl 则在中间惊慌失措。

晚上到了宾馆之后我和 zw 再来规划明天的行程。看了一下，周围似乎没啥好玩的了，有个 aquarium 但是似乎评价不是很高。红警玩家 zw 推荐了珍珠港，因为 Arizona Memorial 在红警里出现过，那我们就去那里了。这里有个问题是 Arizona Memorial 的摆渡船需要预约，而我们没有预约上，但是 anyway 我们还是决定去那里看一下拍个队，随缘吧。说起来这边的 researvation 就很迷，只能预约要么明天的，要么两个星期之后的。预约明天的基本上都被黄牛抢了……

周一

我们本可以选择去大大大早起去 Pearl Harbor 排 Arizona Memorial 的队，但是经过前两天的特种兵旅游，我们决定躺了，吃完饭再去。卡着点 checkout 后，我们去 Sato's Seafood 吃了一个 Poke Bowl。我点了一个 spicy salmon 感觉酱调的非常不错，就是鱼有点少。这家店店内没有桌椅，就在店门口有一两个小桌子，随意配上三四把椅子，我又回忆起了前几天吃 Gina's BBQ 的场景……

吃完饭后打个车去了 Pearl Harbor。门口存了个包后我们就进去排队，幸亏这里的排队是签到制，登记了名字之后不需要排在那里，不过我对排上队不报啥希望了，一来我们吃了饭才来，里面好多人，二来我要赶飞机，如果一个小时内排不上队的话我就看不了了。之后就去里面的珍珠港事件纪念馆随便看看。正当我觉得马上到时间了看不上 Arizona Memorial 的时候，zw 突然发现排到了，哟太凑巧了。

Arizona Memorial 建立在珍珠港事件中被摧毁的 USS Arizona 残骸上，在纪念馆还能看到一些残骸。它不大，里面没有多少东西可以参观。我有时候看到水面上还有一些漂浮的五光十色的东西，zw 告诉我那是不停冒出来的机油，漂浮在水面上，不同地方油层厚度不同，在阳光下反射的光的颜色也不同，这东西还有一个名字，叫做 Tears of the Arizona。Arizona Memorial 附近还有另外一艘战舰，是退役的 USS Missouri，就是在这艘船上，日本正式投降了。将 USS Missouri 停在珍珠港内，算是给故事添上一个句号吧。

Arizona Memorial
Tears of the Arizona

Posted on In Disqus: Word count in article: 1.2k Reading time ≈ 4 mins.

听说今年这两道题比较简单，我就来蹭蹭热度了。 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\) 即可。

  1. 显然有 \(0 \in S\);
  2. 如果 \(0 < \alpha < 1\)，考虑 \(n = \lceil \alpha^{-1} \rceil \geq 2\)，有 \(\sum\limits_{i=1}^n \lfloor i \alpha \rfloor = 1\)，明显不满足要求；
  3. 显然有 \(1 \not\in S\)：令 \(n = 2\) 即可。
  4. 如果 \(1 < \alpha < 2\):
    1. 如果 \(\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\)，矛盾。
    2. 如果 \(\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\) 的构造。所有的图里蓝色为坏人，黄色表示可行路径。

我们先确定第二行的坏人在哪里。这一步直接扫就好了。有两种情况：

  1. Case 1：坏人不在第一列或最后一列。如图所示，A 点和 B 点同行，所以至多有一个坏人。不妨设 B 点没坏人，按照黄色路径走即可。 Case 1
  2. Case 2：坏人在第一列或最后一列。不妨设坏人在第一列，那我们便从上到下依次遍历下图的所有绿色方块，遇到第一个坏人就停止。 Case 2
    1. Case 2-1：我们没有找到任何一个坏人，那么我们可以直接走最后一列即可；
    2. Case 2-2：我们找到了一个坏人，那么按照下面的黄色路径走即可： Case 2-2 A 点左上方的点没有坏人是因为 A 点是我们从上往下扫找到的第一个坏人。

至于 \(n\) 为啥不能小于 3：我们就考虑一个 adversarial 的放坏人的方式，

  • 第一次探索时我把坏人放在你探索的第一个方块上（在第二行）；
  • 第二次探索时我把坏人放在你探索的第一个位于第三行的方块上，这个方块一定和我第一次放坏人的方块不在同一列上，因为你只能从第二行的非坏人方格到第三行。

Posted on In Disqus: Word count in article: 1.9k Reading time ≈ 7 mins.

又是一年 SIGYAO30。今年 SIGYAO30 在 Chicago，一来是因为之前美东美西都举办过 SIGYAO30 了，二来去年商定举办地点的时候，刚好 Chicago 有三个人，于是我们就决定放在 Chicago 了。事实上，我对芝加哥 downtown 印象挺好的，现代的城市，干净的街道，便捷的生活，低廉的物价，丰富的娱乐，多样的美食，就是冬天有点冷，南边不安全……

七年前才毕业，到现在居然已经毕业七年了。上次在芝加哥还是上次。半年不见，如隔六月。这次来芝加哥体验了好多游客项目，我在芝加哥住了一年半，但凡我稍微出门逛逛，也不至于一点也没逛。

Read more »

Posted on In Disqus: Word count in article: 107 Reading time ≈ 1 mins.

这是一道来自王格斯的妙题，有一个 10s 内能说出来的解法。

一个能被 25 个半径为 1 的大圆覆盖的长方形一定能被 100 个直径为 1 的小圆覆盖吗？

Read more »

Posted on In Disqus: Word count in article: 5.4k Reading time ≈ 20 mins.

一想到上一次回国还是疫情前，我心里就直痒痒。疫情期间回国特别麻烦，严格的防疫政策，上天的机票价格，一个个让我知难而退。本想着能不能拿 combo 卡回国，结果被 EB1 突然的排期打了个措手不及。F-1 虽然还没过期，但是交了 140 了，怕是不能用了。幸亏我运气好了一次，抽上了 H1b，这才让我有机会回国喘息一下。去年年底想回国，但是由于刚开始工作不久，假也不多，就此作罢。今年本来想浩浩荡荡把整个 12 月休掉，一来我 check 一般就是这么久，二来加上去年 rollover 的假刚好有这么多，但是由于种种原因，可能更好的选择是拆成两个半个月的假，那么我就九月底先休一次了。我这种长期被 check 体质的人要去办签证了，还是得和老板说一声。今年老板龙颜大悦，直接准了。

规划回国的第一件事，也是最重要的一件事就是约美国签证。我犹豫了好久，到底是在 HK 签好还是国内签好，最后还是决定去 HK。一来我对国内的美领馆的工作人员态度印象不佳，二来感觉国内会很严，但这可能只是我的错觉，可能对于敏感专业的中国人来说，哪里都很严……三来还有一件特别 subtle 的事：我被 check 后只能去 HK 工作，而在我的计划中，我是用护照 + GEP 去 HK，这带来的问题就是，我贴签那几天必须在领馆所在地。如果我在国内签，那么那几天我就只能在国内，没法工作了……理论上是有一些方法去搞定这个这个问题，但是都挺麻烦的……

第二件事，我得有一个合法的身份能在 HK 工作。这里有两种方法，第一种方法是搞一个香港高才，但是准备材料的时候我就直接怂了，还得要我档案所在单位出示一份文件，我连我档案在哪里都记不太清楚了，而且这是和港安通行证挂钩的，我港澳通行证早就过期了，我假期就两周，还不一定能办的下港澳通行证 + 逗留签注，办不下来就 gg 了。第二种是搞一个 HK 签证，用 General Employment Policy（GEP），之后往来 HK 和内地也是用护照。但是 GEP 要求居住在海外的中国公民，还得要我最近一年的出入境记录……说起来我还得在香港办一个居民身份证，但是这怎么这么难约啊？我在芝加哥下午三点钟到它网站上约，它居然让我排！一！个！小！时！的！队！来！预！约！这可是凌晨四点钟的香港啊！（你见过凌晨四点钟的香港的？黄牛：怎么了？）排完队我我更加震惊，我八月份去预约办一个香港身份证，居然只能约到十二月了！为啥十二月还有一个 slot？因为这是刚刚放出来的……昨天放出来的 slot 全部都没了……香港人民这么热爱办居民身份证吗……

第三件事，我得遵守公司的 travel policy。具体是啥我就懒得写了，也挺麻烦的，还得找一堆人签字审批，谁叫国内是 High Risk Country 呢 →_→ 我问能不能去上海，答曰不行。能去上海就太舒服了。

第四件事，就是好好计划假期了！好久没回国了，有太多的人要见，饭局一个接一个，两个星期的假其实不够的，可能只能将将把人见完……

Read more »

Posted on In , Disqus: Word count in article: 516 Reading time ≈ 2 mins.

之前一直想重拾折纸，但是我一直拖……一个原因是我我觉得我的纸不行。之前 折小狗 的时候折着折着纸就破了。研究之后发现纸是有学问的，甚至还有人做了 评测。那这就好办了，是时候展现我的钞能力了！于是我前一段时间买了些纸，包括 Elephant Hide 和 Tant。

这次折的风格和之前不一样了，属于 Tessellation，教程取自 B 站被阿婆。这东西好看是好看，就是打线要打一年，上来就是一个 32x32 的网格 + 32x32 的对角线……不过由于这个动作不需要思考，我就一边看 Netflix 版三体一边打线了。而且，由于几乎所有的 tessellation 都是类似的网格，我甚至可以把一个折好的拆了去折另一个 23333

我第一次用的 Elephant Hide 15x15cm，结果就是中间的方块间隙太大，而且也不方。我又拿 Tant 20x20cm 试了一下，发现效果拔群，我有点不解，按道理不应该是 EH 更好折 Tessellation 吗？我不信邪，想着我第一次可能是没有经验，再次用 EH 折了一次，结果和第一次差不多，中间的方块不太能看……我也不知道是我技术不行，还是 EH 太小了，还是 EH 太厚了？后来反思，我觉得打线打到 16x16 的时候还没啥问题，但是最后的那个横竖 32x32 打线我明显能看出好些地方不太均匀，我甚至能感觉纸的曲率都变了……论非欧几何在折纸中的应用？？？不过不得不说，这两种纸都挺耐折的，要我之前的纸怕是早就破了。手感上 EH 更厚实，Tant 比较软。

最后就放几张图吧……从左到右分别是卖家秀、Elephant Hide v2 和 Tant，感觉 Tant 版除了是单色所以层次感差了点以外，其它和卖家秀差不多了。

卖家秀
Elephant Hide v2
Tant

Posted on In Disqus: Word count in article: 556 Reading time ≈ 2 mins.

某 quantum gravity 专家 cls 最近可意气风发。自打决定在湾区再多待一阵之后，cls 便研究起了买车。当然，cls 可以选择微啃一下买辆法拉利，但是作为一个新时代独立自主的男性，cls 没有选择啃老，而是先租一辆小破车体验一下，一来经济上稍微划算那么一丢丢，二来 cls 刚拿驾照没多久，还是先练练手吧。

刚好趁着与胡老师约饭的机会，cls 开着他的小破车从 Berkeley 来到了南湾。饭后大家一致决定（其实就脸哥和 cls）去 Hakone 赏花。但是去程就犯难了，谁来坐 cls 的车呢？现在我们有三位司机：

  • 以 cls 为代表的新司机，购买高额保险，体验刺激人生；
  • 以脸哥为代表的老司机，表演精湛技术，偶尔忘看红灯；
  • 以 cxq 为代表的 AI 司机，只需付费升级，纵享智慧 AI。

等王老爷子从饭馆出来，三位司机都向他抛出了橄榄枝。他将面临艰难抉择：到底该 pick 哪位司机？谁将助力完成他赏花的梦想？是初生牛犊不怕虎的他？还是经验老练的她？抑或是沉着冷静来自钞能力的它？ （广告之后，精彩继续）

然而不幸的事情还是发生了，晚上回家的路上，志在必得的新司机 cls 带着我和王老爷子回家，车上三位加起来驾驶时长不超过 30h，结果在高速上遇上了年轻人的第一次高速事故，所幸人都没事。下午还在对着车型高谈阔论侃侃而谈的 cls，立马开始仔细钻研保险。我们以及和我们相撞的车都还好，但是在我们相撞的同时，我看着一辆车侧着在我们左前方飞过，地上还有阵阵火花，还是有点恐怖。我也不知道这辆车和我们到底有啥关系，我只能猜测是后车看到前面有车相撞，心里一紧一转方向盘，于是前车没事自己 gg 了。

0%