奇偶校验与哥尼斯堡七桥
通过黑白棋通信
- 徒弟在桌上摆 7 枚黑白棋，观众可以翻转其中 1 枚（或不翻转）
- 魔术师蒙着眼睛，什么都没看见，却能立刻说出观众有没有翻转棋子
- 徒弟和观众不发一言，魔术师也不知道观众有没有翻转
- 信息是通过棋子的摆法传递的
思考题答案
徒弟如何传递信息
- 徒弟在观众摆放的 7 枚棋子中，数出黑棋的个数
- 黑棋数是奇数，就添黑棋；黑棋数是偶数，就添白棋
- 无论哪种情况，最终 8 枚棋子中黑棋必为偶数个
- 观众的行动有三种：
- 翻转白棋 → 黑棋增加 1 枚，变奇数个
- 翻转黑棋 → 黑棋减少 1 枚，也变奇数个
- 不翻转棋子 → 黑棋仍是偶数个
- 魔术师摘下眼罩数出黑棋个数：奇数 → 「翻转过棋子了」，偶数 → 「没有翻转」
- 徒弟摆成「黑棋为偶数」，摆成「黑棋为奇数」也行，只要事先商量好
奇偶校验
从戏法到通信
- 把白棋看作 2 进制的 0，黑棋看作 2 进制的 1
- 徒弟 = 发送方，魔术师 = 接收方，翻转棋子的观众 = 干扰通信的噪音（noise）
- 徒弟放的那 1 枚棋子，在通信领域称为奇偶校验位（parity bit）
- 魔术师通过检查棋子的**奇偶性（parity）**判断是否发生通信错误
- 校验位设为偶数还是奇数，是发送方和接收方之间事先约定的通信规则
奇偶校验位将数字分为两个集合
7 枚棋子的排列法总共 2⁷ = 128 种
其中一半（64 种）是黑棋为偶数个，另一半（64 种）是黑棋为奇数个
128 种组合被分成 2 组
徒弟添加的那 1 枚棋子，起到了标识当前摆法属于哪一组的作用
摆黑棋或摆白棋两种情况，区分两个组
用代码验证分组
#ruby
# 7 枚棋子的 128 种摆法，按黑棋个数的奇偶分组
even = odd = 0
(0..127).each do |bits|
black = bits.to_s(2).count("1")
black.even? ? even += 1 : odd += 1
end
puts "黑棋偶数个的摆法: #{even}" # 黑棋偶数个的摆法: 64
puts "黑棋奇数个的摆法: #{odd}" # 黑棋奇数个的摆法: 64
# 徒弟加校验位：让 8 枚的黑棋数恒为偶数
def add_parity(bits)
black = bits.to_s(2).count("1")
black.even? ? bits : bits | (1 << 7)
end
(0..127).each do |bits|
raise "校验位失效" unless add_parity(bits).to_s(2).count("1").even?
end
puts "校验位全部有效" # 校验位全部有效
寻找恋人的思考题
思考题（寻找恋人）
- 王国里有 8 个村子（A~H），村之间有道路相连
- 恋人住在其中一个村，每过 1 个月顺着道路去另一个村，选哪个村是随机的
- 已知 1 年前（12 个月前）恋人住在 G 村
- 求这个月恋人住在 A 村的概率
提示：先试算较小的数
- 12 个月前（第 0 次移动）恋人在 G
- 11 个月前（第 1 次移动）恋人在 G 的某个邻居
- 逐次往前推，只关心目的地，不关心路线
思考题答案
- 从第 4 次移动开始出现规律：
- 奇数次移动时，恋人在奇数村
- 偶数次移动时，恋人在偶数村
- 12 是偶数，所以恋人现在在偶数村，不在 A 村
- 答案：概率为 0
- 从第 4 次移动开始出现规律：
回顾
若按「路线」考虑，就得研究很多种可能
换成按「目的地」考虑，问题迎刃而解
以 G 为起点，移动奇数次到达的村子叫「奇数村」，偶数次到达的叫「偶数村」
A~H 这 8 个村没有哪个既属奇数村又属偶数村，且每个村必属其中之一
这是兼具排他性和完整性的分类
从奇数村移动 1 次就到偶数村，从偶数村移动 1 次就到奇数村
本题也是奇偶校验的一个例子
用代码验证这个分类的性质
#ruby
# 奇数村 A,C,F,H；偶数村 B,D,E,G（照原书图 3-8）
odd_v = %w[A C F H]
even_v = %w[B D E G]
# 分类的两个性质：
# 1) 排他性：没有村子同时属于两组
# 2) 完整性：8 个村子每个都恰好属于一组
puts "两组无交集: #{(odd_v & even_v).empty?}" # 两组无交集: true
puts "覆盖全部8村: #{(odd_v + even_v).sort == ('A'..'H').to_a}" # 覆盖全部8村: true
# 从奇数村移动 1 次到偶数村，从偶数村移动 1 次到奇数村
# 12 次移动是偶数次 -> 落在偶数村（B,D,E,G）
land = even_v
puts "12次移动后所在组: #{land.join(', ')}" # 12次移动后所在组: B, D, E, G
puts "A 在这一组里吗: #{land.include?('A')}" # A 在这一组里吗: false
puts "恋人在 A 村的概率: 0" # 恋人在 A 村的概率: 0
铺设草席的思考题
思考题（在房间里铺设草席）
- 用图中右下角所示的草席能正好铺满房间吗？前提是不能使用半张草席
- 如果不能，请说明理由
提示：先计算一下草席数
- 以「半张草席」为单位计算房间面积
- 1 张草席由 2 个半张组成
- 若房间面积按半张草席算得奇数，说明不能正好铺满
- 计算结果是 62 张半张草席，但 62 是偶数，光靠奇偶性判断不了
思考题答案
- 以「半张草席」为单位给房间涂色区分
- 黑色的半张草席：30 张
- 白色的半张草席：32 张
- 一整张草席由 1 黑 + 1 白组成
- 黑白数量不等（30 ≠ 32），无论用几张草席都铺不满
- 面积相等不代表能拼出来 —— 需要更细的分类
一笔画的思考题
思考题（哥尼斯堡七桥问题）
- 哥尼斯堡小城被河流分割成 4 块陆地，人们建了 7 座桥
- 要找出走遍 7 座桥的方法，必须遵守：
- 走过的桥不能再走
- 可以多次经过同一块陆地
- 可以以任一陆地为起点
- 不需要回到起点
- 能走遍就说明方法，不能就证明
提示：考虑入口和出口
- 要通过 1 个顶点，这个顶点必须有 2 条边，即「入口边」和「出口边」
- 1 个顶点关联着多条边，但每通过顶点一次，这个顶点就减去 2 条边
- 这就是暗藏玄机之处
思考题答案
顶点关联的边数称为该顶点的度数
度数为偶数的顶点称为偶点，度数为奇数的称为奇点
顺着边走，在经过的边的端点处打钩并减去顶点度数 —— 称为「边走边减」
出发时起点度数减 1
途中每经过一个顶点，度数减 2（经过入口边和出口边）
到达终点时，终点度数减 1
每次经过顶点都减 2，所以经过的顶点的奇偶性不变
两种情况
- 起点和终点相同：一笔画成意味着所有顶点度数变为 0（偶数），所以图中顶点都是偶点
- 起点和终点不同：经过的顶点全是偶点，只有起点和终点是奇点，图中只有 2 个奇点
命题：「可以一笔画成」=「所有顶点都是偶点，或者有 2 个奇点」
逆命题也成立（此处省略证明）
回到哥尼斯堡七桥：数一下各顶点关联的边数，4 个顶点都是奇点
4 个奇点 ≠ 0 个或 2 个奇点，因此走遍 7 座桥不可能
欧拉的论断
重点在于：不反复试验也能证明不能一笔画成
不用频繁试走各种路径，只要观察各顶点的度数就行
欧拉证明中蕴含的重要思维方法：观察边数时，着眼点在「数的奇偶性」上
不是 1 条、3 条、5 条这样分散地思考，而是概括为「奇数条」整体考虑
这又是奇偶校验的一个例子
用代码验证：枚举所有路径 + 判定奇点数
#ruby
# 哥尼斯堡七桥多重图：4 个顶点 7 条边，度数 (5,3,3,3) -> 4 个奇点
BRIDGES = [["A","B"], ["A","B"], ["A","D"], ["A","D"], ["B","C"], ["A","C"], ["D","C"]]
def degrees
d = Hash.new(0)
BRIDGES.each { |u, v| d[u] += 1; d[v] += 1 }
d
end
def odd_vertices
degrees.select { |_, v| v.odd? }.keys
end
# 枚举所有不重复边的走法
def all_walks
results = []
walk = lambda do |path, used, cur|
if used.size == BRIDGES.size
results << path.dup
return
end
BRIDGES.each_with_index do |(u, v), i|
next if used.include?(i)
if cur == u then nxt = v
elsif cur == v then nxt = u
else next
end
path << nxt
walk.call(path, used + [i], nxt)
path.pop
end
end
BRIDGES.map(&:first).uniq.each { |s| walk.call([s], [], s) }
results
end
puts "各顶点度数: #{degrees.sort.to_h}" # 各顶点度数: {"A"=>5, "B"=>3, "C"=>3, "D"=>3}
puts "奇点: #{odd_vertices.sort.join(', ')}" # 奇点: A, B, C, D
puts "奇点个数: #{odd_vertices.size}" # 奇点个数: 4
puts "走遍7桥的走法数: #{all_walks.size}" # 走遍7桥的走法数: 0
# 欧拉判定：奇点个数为 0 或 2 才能一笔画成
euler = (odd_vertices.size == 0 || odd_vertices.size == 2)
puts "能一笔画成? #{euler}" # 能一笔画成? false