#import "../../lib.typ": *

= 鸽巢原理

== 鸽巢原理简单形式

#showybox()[
  如果要把n+1 个物体放进n个盒子，那么至少有一个盒子包含两个或更多的物体。

]

#showybox(title: [中国剩余定理])[
设m和n是互素的正整数，并设a和b为整数，其中$0≤a≤m-1$以及 $0≤b≤n-1$。于是，存在正整数x，使得x除以m 的余数为a，并且x除以n 的余数为b;即x可以写成$x=p*m+a$的同时又可写成$x=q*n+b$ 的形式，这里，p和q是两个整数。
]

== 鸽巢原理加强版

#showybox()[
设 $q_1，q_2$，是正整数。如果将$q_1+q_2+q_3+……+q_n-n+1$个物体放入n个盒子内，那么或者第一个盒子至少含有$q_1$个物体，或者第二个盒子至少含有$q_2$个物体，…，或者第n个盒子至少含有$q_n$个物体。  
]

#showybox(title: [推论])[
设n和r都是正整数。如果把$n(r-1)+1$个物体分配到n个盒子中，那么至少有一个盒子含有r个或更多的物体。

可以用另一种方法陈述这一推论中的结论，即平均原理: 如果n个非负整数$m_1,m_2,……,m_n$的平均数大于$r-1$，即$ (m_1+m_2+...+m_n)/n ≥ r - 1 $


那么至少有一个整数大于或等于r。
]

#showybox(title: [一个不同的平均定理])[
  如果n个非负整数$m_1,m_2,……,m_n$的平均数小于r+1，即$ (m_1+m_2+...+m_n)/n ≤ r - 1 $
那么其中至少有一个整数小于 r+1。
]

#showybox(title: [另外一个平均定理])[
  如果n个非负整数$m_1,m_2,……,m_n$的平均数至少等于r，那么这n个整数$m_1,m_2,……,m_n$至少有一个满足$m_i≥r$
]

#pagebreak()
== 课后习题

#showybox(
  title: [课后习题]
)[
  @ch1
]