Introductory Combinatorics 5th Solutions Chapter1 7~13

Richard A.Brualdi 组合数学5th 课后习题答案

其实这篇文章只是用来记录我解题思路的笔记。

第一章 什么是组合数学

7.题目略
step1：若a即是m的因子也是n的因子，即必然存在k使： k x a = m ，k x a = n 成立，此时看b是m还是n的因子，若b为m的因子，则必然找到 j 使 j x b = m ， 即可以用 j 个a x b 的牌组成 a x m 的牌 ，又因为 a是n的因子，着必然可以用 k 个 a x m 的牌将棋盘完美覆盖。
step2:若b为n的因子，同理，先组成a x n 的牌，再将棋盘完美覆盖。
step3：若a 并不同时是m 和 n 的因子，则可以考虑以下两种情况：
a）a和b都是m的因子，但是a不是n的因子。此时返回去看step1，在组成a x m的牌后，因为a不是n的因子，显然不能使棋盘完美覆盖
b) a和b都是n的因子，但是a不是m的因子。此时返回去看step2，在组成a x n的牌后，因为a不是m的因子，显然不能使棋盘完美覆盖
step4:因为a已经假设为b的因子，所以不存在a是b的因子，b是m的因子，但是a不是m的因子的情况。（在默认m , n > a,b 的情况下）。题目中在“当且仅当”的条件下完美覆盖的证明完毕。

8.题目略
step1：个人解读以下“平凡完美覆盖”，即完美覆盖时，所有的牌都朝着一个方向，即牌的短边，假设为a，必然满足 k x a = n or m ，且长边b为 m or n 的因子。题目已假设a为b的因子了。
step2：题目可以翻译成，当存在完美覆盖时，当且仅当因子a同时为m 和 n的因子，且b为m 或 n 的因子。即转变为证明题目7。

9.题目略
step1：举出一个反例即可，棋盘6x8，a=2,b=3，棋盘存在完美覆盖，但是不存在平凡完美覆盖。

10.验证不存在2阶幻方
step1：
设 a,b,c,d 且 a,b,c,d为不相等整数，于1，2，3，4中。不妨如下排列：

列出等式：
a+b = c+d
a+c = b+d
a+d = c+b
相加得：3a = b+c+d
两边同时加a，得：4a=a+b+c+d
得：a=2.5，但是a只能为整数，所以2阶幻方不存在。

11.利用loubere方法构建7阶幻方：

12.利用loubere方法构建9阶幻方：

13.构造一个6阶幻方
使用神奇得strachey法(真的很神奇)：
step1：用 1~9，10 ~ 18 ，19 ~ 27 ， 28 ~ 36 ，四组数字，使用loubere法生成4个3阶幻方，然后如图摆放：

step2：对调如图所示位置就形成了一个6阶幻方了！