题目
把 1, 2, 3 这 3 个数字填入 3×3 方格,使每行、每列都恰好出现 1, 2, 3 各一次(即 3 阶拉丁方)。
此外还要满足以下 5 条不等号约束:
- (1,1) < (1,2)
- (2,1) > (2,2)
- (3,2) < (3,3)
- (1,3) > (2,3)
- (2,2) > (3,2)
请给出满足上述所有条件的填法(可以证明此填法唯一)。
解法
分析:把方格记作 a b c / d e f / g h i。约束 (2) d > e 与 (5) e > h 可串成 d > e > h;d、e、h 三数都取自 {1, 2, 3},所以只能 d = 3, e = 2, h = 1——这是突破口。
按拉丁方规则逐格推:第 2 列 {e, h, ?} ⇒ b = 3;第 2 行 ⇒ f = 1;第 3 行剩 {g, i} = {2, 3},但第 1 列已有 d = 3,故 g = 2, i = 3;第 1 行 a ≠ 2, 3,得 a = 1, c = 2。
验证剩余 (1)(3)(4) 成立,唯一解 1 3 2 / 3 2 1 / 2 1 3。
d > e > h (① 三数取自 {1,2,3})=d=3, e=2, h=1第 2 列:{e=2, h=1, b} (②)=b=3第 2 行:{d=3, e=2, f} (③)=f=1第 3 行:{g, h=1, i},第 1 列禁 3 (④)=g=2, i=3第 1 行:{a, b=3, c},第 1 列禁 3,2 (⑤)=a=1, c=2132321213
方法
练一练
把 1, 2, 3 填入 2×3 方格,使每行恰好出现 1, 2, 3 各一次;要求 (1,1) < (1,2) < (1,3) 且 (2,1) > (2,2) > (2,3)。请写出第 2 行从左到右的数字(用空格分隔)。