组合数学第一次课笔记

时间:2022-08-17 14:23:25

1、  幻方:任意行,任意列,任意对角线的和(记做幻方和)都相等。

根据这个定义很容易知道幻方和可以推导出来

设有一个的幻方 每一行有n个数,假设从1到n2的数都是连续的,

则所有数的和为

如果即每一行的和为s(很明显s等于幻方和)

则有 

       于是我们就得到这种从1到n2连续数字的幻方和为  

2、  二阶幻方和存在吗? 假如存在的话,则幻方和为 

假设幻方的构造如下:

 a 

 b 

 c

 d 

       则a + b = 5

          a + c = 5

       所以有 b = c 矛盾

故不存在上面假设形势下的2阶的幻方

有数学家已经证明了3阶及以上的幻方都是存在的

3、  那么怎么构造一个三阶幻方了

杨辉的方法是

    1

  4   2

  7    5  3                 

    8      6

          9           

 

上面错看排好以后 1,9和7,3分别换位置

     9

  4      2

   3  5 7                

    8    6

       1

整理一下便有

   4 2 9

   3 5 7

   8 6 1

但是这只适合这一种情况。。

西方的一个数学家提出了一个适合3m阶的幻方构造方法

先固定1的位置,然后后面的数字依次从左下到右上的方向在右上的位置放置下一个数字,如果出界了就放到对应行或者列的循环后的位置处,如果这个位置有数字了就放到前面那个数字的下面

 

    

  1 

    

 

 

 

 

 

 

 

    

   1

    

 

 

 

 

 

 2

 

    

   1

    

3

 

 

 

 

2

 

    

   1

    

3

 

 

4

 

2

 

    

   1

    

3

5

 

4

 

2

 

    

   1

   6

3

5

 

4

 

2

 

    

1   

6   

3

5

7

4

 

2

 

8   

   1

   6

3

5

7

4

 

2

 

  

8   

   1

   6

3

5

7

4

9

2

 

这和杨辉得到的幻方不太一样

 

   4 2 9

   3 5 7

   8 6 1

其实上下翻转一下就是一样的了。

一件T恤上可以印刷多少幻方了?

考虑到每次旋转90度都可以翻转,故共有 4 * 2 = 8个

4、一一对应的应用

 组合数学第一次课笔记

世界杯复赛中十六支球队进行单场淘汰赛,直至决出冠军,若不考虑决赛阶段的第三名争夺赛,请问一共要踢多少场比赛?

可与从上图中直接数则共有15场比赛

 

 

显然这是不用一一枚举的,对于单场淘汰赛来讲 一场比赛要淘汰一支队伍

所以每场比赛和淘汰的球队一一对应 总共只有一个冠军 共淘汰了15之球队 故共需15场比赛

同理224个国家的足球对进行单场淘汰赛 则需要进行223场比赛。

 

5、哥尼斯堡七桥问题

欧拉证明了共有0中方案

并发表了全世界第一篇有关图论的论文,并得到一个结论就是

如果在一张图上想要一笔画出所有的边的话他的充分必要条件是

A、首先你的点要连通

B、  奇数点(连接的边数是奇数)的个数要么是0要么是2,为0的时候从任一边出发都可以,为2的时候必须从一个奇数点出,并最终到达另一个奇数点