问题月题集3的解 到期：星期二，2月22日下午9点 问题1缸包含75个白色球和150个黑球，当至少2个球在缸中时，您重复以下操作，您 去除任意地选择的2个球，那么： ·二个球中如果至少一是黑色的。那么您放弃一黑球并且放同另一个黑球到缸里。 “两个球是白色的，那么够故弃它门两个，并且放个新的黑球到缸里。 正明红从未到达它是空的，除了一个黑球的状态 解：我门使用归纳法证明。令P()是缸总是包含奇数个白球的命题。 基例：最初，缸包含75个白色球，是一个奇数，因此P0是真实的. 归纳步：假设红在步以后包含奇数的白色球。如果存在比2个球少剩余，然后过程结束。 否则，有然后二种情况 1您取出至少一个黑球。然后凰球的数量减少一个，并且白色球的数量是未改变的。所 以，白色球的数量依然是食数。 2您取出两个白色球，然后黑球的数量增加一个，并且白色球的数量减少两个。再次， 白色球的数量依然是奇数。 因此，杠在叶1步以后仍然包含奇数的白色球。由归纳法得，缸总是包含奇数个白色 球。所以，因为零是偶数，缸不可能保留着一个国球和零个自色球 问题2难题玩具包含写在小圆盘上的1。一，35。盘核安排在一条卵形轨道，且没有 间原，以便盒整体序列可能在轨道附近顺时针或逆时针滑动， PDF文件使用“pdfFactory Pro”试用版本创建，fineprint,cn
问题问题集 3 的解 到期：星期二， 2 月 22 日下午 9 点 问题 1 缸包含 75 个白色球和 150 个黑球。 当至少 2 个球在缸中时，您重复以下操作。 您 去除任意地选择的 2 个球，那么： •二个球中如果至少一是黑色的，那么您放弃一黑球并且放回另一个黑球到缸里。 •两个球是白色的，那么您放弃它们两个，并且放一个新的黑球到缸里。 证明缸从未到达它是空的，除了一个黑球的状态。 解：我们使用归纳法证明。 令 P (n)是缸总是包含奇数个白球的命题。 基例： 最初，缸包含 75 个白色球，是一个奇数，因此 P (0)是真实的。 归纳步： 假设缸在 n 步以后包含奇数的白色球。如果存在比 2 个球少剩余，然后过程结束。 否则，有然后二种情况： 1.您取出至少一个黑球。然后黑球的数量减少一个，并且白色球的数量是未改变的。所 以，白色球的数量依然是奇数。 2.您取出两个白色球。 然后黑球的数量增加一个，并且白色球的数量减少两个。 再次， 白色球的数量依然是奇数。 因此，缸在 n+ 1 步以后仍然包含奇数的白色球。 由归纳法得，缸总是包含奇数个白色 球。 所以，因为零是偶数，缸不可能保留着一个黑球和零个白色球。 问题 2 难题玩具包含写在小圆盘上的 1，…， 35。 圆盘被安排在一条卵形轨道，且没有 间隙，以便盘整体序列可能在轨道附近顺时针或逆时针滑动。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
Disks slide around track. ®5020o0aX Turning dial reverses the order of four disks. 另外，轨道上有一个堂是四张盘的圆形罗盘。这个罗盘可以被转动180度，反转四张 在轨道上的那部分置盘。例如。如果罗盘在上面配置核转动了，那么34,3衫。1,2的 次序将成为2,1,35,34. 假设难题最初在以上状志暴示，数字是逆时针增加。证明，没有操作序列仅交换1和 2世的作用，当把所有其他盘留在按同一顺序时。 解：同恩的每种配置联系在一起数字的排列1，，35，通过递时针顺序取数字， 在罗盘中间位置。因此，例子配置对应于捧列： 123..35 现在我们使用在操作的数量上的归钠法。令P()是在操作以后，有偶数反向的金题。 基创子：最初，有零个反向。因为零是偶数，P(0)为真： 自纳步：假设在n步以后有偶数的反向。现在有三种情况米考虑： ·假设罗盘按转动180度。这变换排列 51525354·.53053353H535 到排列： 5355345384,··53过58251 这共计交换5s和数以及到与54：每次交换支变了反向的奇偶性，因此在两次交换后，仍 然有偶数的反向， Pf文件使用"pdfFactory Pro”试用版本创建w.fineprint,cn
另外，轨道上有一个宽是四张盘的圆形罗盘。 这个罗盘可以被转动 180 度，反转四张 在轨道上的那部分圆盘。 例如，如果罗盘在上面配置被转动了，那么 34， 35， 1， 2 的 次序将成为 2， 1， 35， 34。 假设难题最初在以上状态显示，数字是逆时针增加。 证明，没有操作序列仅交换 1 和 2 盘的作用，当把所有其他盘留在按同一顺序时。 解：同难题的每种配置联系在一起数字的排列 1，…， 35，通过逆时针顺序取数字， 在罗盘中间位置。 因此，例子配置对应于排列： 1 2 3… 35 现在我们使用在操作的数量上的归纳法。令 P (n)是在 n 操作以后，有偶数反向的命题。 基例子：最初，有零个反向。 因为零是偶数， P (0)为真。 归纳步： 假设在 n 步以后有偶数的反向。 现在有三种情况来考虑： •假设罗盘被转动 180 度。 这变换排列 到排列： 这共计交换 s35 和 s2 以及 s1 与 s34。每次交换改变了反向的奇偶性，因此在两次交换后，仍 然有偶数的反向。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
·假设数字被转动到沿着轨道顺时针的一个位置。这变换排列 81828384··.832833834835 到排列： s2S384···83283353453581 这个题转恰好4对盘子，8和每个其他盘子。这改变反向的奇偶性34次，图下一个 每数个反向。 ·同样，逆时针转动一个位置，绿留4对的顺序，在此留下一个偶数的反向。 由归纳法得，反向的数量总是偶数的。所以。1和2被交换（有1反向）的配置是不能 符到的。 间题3规则的每酬52素牌，安排如下： A92..K9A424,.K泰A◆2◆..K★A◇20..K0 在完美的洗牌中，一别牌首先教划分成二堆。一堆含前面的26张卡片，另一堆包含其他底 部的26张牌。这两堆然后被再结合称为一刚牌，通过完美地交织他门： 因为新的顶面卡片可能来自任一个站卡片的堆，这个交请的过程可以用二个不同的方式 完成。因此在完美的徒牌序列后，可以获得许多不同的排列的一刚牌，正明。没有完美的 洗牌序列把一别牌成为以下顺序： A92w..K9A424..K泰A◇20..K◇A◆2◆..K◆ 解：我们使用归纳法。定文在第张的卡片和第52-)个位置的卡片为对面的。因此， 例如，顶面卡片是在底下卡片对面，第二张卡片是和最后一张卡片上一底对面，并且在甲板 中间的二素卡片是在被此对面。令P()是对面的卡片是同一种颜色的命题。 基例：在初始配置中，红心和梅花对面。凰桃和方片对面。所以。所有相反卡片是同一种 P诉文件使用”pdfFactory Pro”试用版本创建.finsprint,cn
•假设数字被转动到沿着轨道顺时针的一个位置。 这变换排列 到排列： 这个翻转恰好 34 对盘子， s1和每个其他盘子。 这改变反向的奇偶性 34 次，留下一个 偶数个反向。 •同样，逆时针转动一个位置，保留 34 对的顺序，在此留下一个偶数的反向。 由归纳法得，反向的数量总是偶数的。 所以， 1 和 2 被交换(有 1 反向)的配置是不能 得到的。 问题 3 规则的每副 52 张牌，安排如下： 在完美的洗牌中，一副牌首先被划分成二堆，一堆含前面的 26 张卡片，另一堆包含其他底 部 的 26 张 牌 。 这 两 堆 然 后 被 再 结 合 称 为 一 副 牌 ， 通 过 完 美 地 交 织 他 们 ： 因为新的顶面卡片可能来自任一个 26 卡片的堆，这个交错的过程可以用二个不同的方式 完成。因此在完美的洗牌序列后，可以获得许多不同的排列的一副牌。 证明，没有完美的 洗牌序列把一副牌成为以下顺序： 解：我们使用归纳法。 定义在第 i 张的卡片和 第(52 −i) 个位置的卡片为对面的。 因此， 例如，顶面卡片是在底下卡片对面，第二张卡片是和最后一张卡片上一张对面，并且在甲板 中间的二张卡片是在彼此对面。 令 P (n)是对面的卡片是同一种颜色的命题。 基例： 在初始配置中，红心和梅花对面，黑桃和方片对面。 所以，所有相反卡片是同一种 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
氟色。 归销步：假设所有相反卡片是同一种膜色。考虑一刚牌中的一种任意配置 C1C2C3··C52 一个完美的洗韩把一别牌图到以下的顺序， CC27C2C28C3C29,·,C25C61C26C52 C27C1C28C2C29C3··.C51C25C52C26 在两种情况下，同一张卡片保持对面：和，⊙和©1等等。因此，特别是，在卡片对 面仍然是同一种颜色. 由归纳法得，在卡片对面总是同一种飘色。所以，因为那里所有相反卡片是不同的测 色，红心，黑桃，将花，方片得配置是不能得到的。 问题4正明关于最大公因子的以下基本事实 (arda,地)-k·d(a,b.对于所有k之的0. 解：最小的正的值是： s·(ka)+t(kb)=k·(s·a+t.b 在多有的所有s。【∈Z是k倍最小的正值 s·a+t.b 在所有s【∈Z,第一个数量是d(ka,b).并且第二是d(a,b).所以， ged (ka,kb)-kged (a,b). (b)cda,bPod(a+k地，bh,对于所有k的EZ, 解：我们说明，a和b的每个线性组合是一个a+kb和b的线性组合和反之亦然。 ·如果x一知+也，那么x一'位+kh)+tb,这里s'一s和”一1-sk. ·如果X=s'·ab+b,那么X=+b,这里s=s和1=1+sk: 因此，特别是，最小的正的线性组合是相等的，如此d(a,bFd(a+kb,b): 间题5这是一些很长的合数： 114.115.116.11711&119,120.121.122123.124.125.126 证明票里存在任意长的合数。考感比稍微大一点的数字！这里 n!=n(n-1)…3.2.1 PDF文件使用“pdfFactory Pro”试用版本创建题，fineprint.cn
颜色。 归纳步： 假设所有相反卡片是同一种颜色。 考虑一副牌中的一种任意配置： 一个完美的洗牌把一副牌留到以下的顺序： 在两种情况下，同一张卡片保持对面： c1和 c52、c2 和 c51等等。 因此，特别是，在卡片对 面仍然是同一种颜色。 由归纳法得，在卡片对面总是同一种颜色。 所以，因为那里所有相反卡片是不同的颜 色，红心，黑桃，梅花，方片得配置是不能得到的。 问题 4 证明关于最大公因子的以下基本事实： (a) gcd (ka，kb) = k · gcd (a， b)，对于所有 k>的 0。 解：最小的正的值是： 在多有的所有 s， t ∈ Z 是 k 倍最小的正值 在所有 s， t ∈ Z。 第一个数量是 gcd (ka，kb)，并且第二是 gcd (a， b)。 所以， gcd (ka，kb) = kgcd (a， b)。 (b) gcd (a， b)= gcd (a +kb， b)，对于所有 k 的∈ Z。 解： 我们说明， a 和 b 的每个线性组合是一个 a +kb 和 b 的线性组合和反之亦然。 •如果 x = sa + tb，那么 x = s’ · (a +kb) + t’b，这里 s’ = s 和 t’ = t − s’k。 ·如果 x = s’ · (a +kb) + t’ b，那么 x = sa + tb，这里 s = s’和 t = t’ + s’k。 因此，特别是，最小的正的线性组合是相等的，如此 gcd (a， b)= gcd (a +kb， b)。 问题 5 这是一些很长的合数： 114,115,116,117,118,119,120,121,122,123,124,125,126 证明那里存在任意长的合数。考虑比 n! 稍微大一点的数字! 这里 。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
解：令k是某一自然数这样1<kS。我门知道材(+k),因为材并且kk。因此， 数字nl42,l+3,l+4,…,nl+n都是合数。这是是-1违贯合数序列.由于我们 可以任意地透择，我们知道任意长度的合数序列是存在的， 间题6这是一个非常有题的游戏。初始的时候，有一个凰板有数字1309和1729写在上面。 现在你和我轮流：你先来，在轮到每个玩家的时候，他或地必须在黑板上写一个新的正整数， 那个正整数是和已经有的两个正整数的差。第一个不能创建新的数字的输掉游戏。 例如，首先移动必须是1729一1309=420。然后我能或者玩1309420-=889或者 1729420-1309,等等. ()证明在黑版上写的每个数学是7的倍数，小于或等于1729。 解：我门使用归钠法。令P()是在n步以后，在黑板上的每个数字是1729和1390的一 个正的线性组合的合卷。 基例子：P(0是真实的，因为1729和1390是1729和1390年的平凡的线性组合： 归销步：假设，在n步以后，在黑板上的每个数字是1729和1390的一个正的线性组合， 由于： ·规则要求数字是正的。 ·新的数字必颈是二个己经在凰板上的数字的差，它们自己是129和1390的线性组合， 由假定得。并且线性组合的差是另一个线性组合。 由归纳法得，在黑板上的每个数字是129和1390的一个正得线性组合。并且129 和1390的每个正得线性组合是rd(1729,1390)-7的倍数。 (色】正明一切7的倍数小于或等于1729，在湖戏结来的时候常在黑板上， 解：设X最小的在比赛结束时候的数字。由除法算法得，存在整数q和x以便，1729-q四+ r这里0Sx<x。当没有更多的动作是有可能，1729-×必领已经在黑板上的，侧此，必领 使1729-2×：·。·1729-(g-1)×:然而，1729-g×=x不能在黑板上的，因为x< 装且x则是定义为最小数目。唯一的解释是的x■0，这意味看黑11？29·由对成说法， ×11390。因此，×是一个×和y的公约数。1729和1390仅有的公钓数分别为1和7，并月 愿的前面部分得x不能是1。因此。在游戏结束的时候，7是在黑板上的。由于没有更多的动作 是有可能，1729-7,1729-2：7，···，7,0，都必领那在厘版上。所以每个7 的正整数小于或等于1729在游戏结熏的时候是在黑板上的， (c谁取了 解：在凰板上由17297=247个数字，在游戏结束的时候。因此。有247-2=245移动。因 为您首先去，您也得到最后移动，在赢得游戏。 间题7证明以下定理。 定理：如果d(a,b)■l,那么8cd(atb,-b)■或2. 解：因为eda,b)=1,那里存在整数s和1，以便： s·a+t.b=1 PF文件使用"pdfFactory Pro”试用版本创建w.fineprint.cn
解：令 k 是某一自然数这样 1 < k ≤ n。 我们知道 k| (n! + k)，因为 k| n! 并且 k|k。 因此， 数字 n! +2， n! +3， n! +4，…， n! ＋n 都是合数。这是是 n−1 连贯合数序列。 由于我们 可以任意地选择 n，我们知道任意长度的合数序列是存在的。 问题 6 这是一个非常有趣的游戏。初始的时候，有一个黑板有数字 1309 和 1729 写在上面。 现在你和我轮流；你先来。在轮到每个玩家的时候，他或她必须在黑板上写一个新的正整数， 那个正整数是和已经有的两个正整数的差。第一个不能创建新的数字的输掉游戏。 例如，您首先移动必须是 1729－1309 ＝420。然后我能或者玩 1309-420=889 或者 1729-420=1309，等等。 (a) 证明在黑板上写的每个数字是 7 的倍数，小于或等于 1729。 解： 我们使用归纳法。 令 P (n)是在 n 步以后，在黑板上的每个数字是 1729 和 1390 的一 个正的线性组合的命题。 基例子： P (0)是真实的，因为 1729 和 1390 是 1729 和 1390 年的平凡的线性组合。 归纳步： 假设，在 n 步以后，在黑板上的每个数字是 1729 和 1390 的一个正的线性组合。 由于： •规则要求数字是正的。 •新的数字必须是二个已经在黑板上的数字的差，它们自己是 1729 和 1390 的线性组合， 由假定得。 并且线性组合的差是另一个线性组合。 由归纳法得，在黑板上的每个数字是 1729 和 1390 的一个正得线性组合。 并且 1729 和 1390 的每个正得线性组合是 gcd (1729,1390) =7 的倍数。 (b)证明一切 7 的倍数小于或等于 1729 ，在游戏结束的时候都在黑板上。 解：设 X 最小的在比赛结束时候的数字。由除法算法得，存在整数 q 和 r 以便， 1729= qx + r 这里 0 ≤ r <x。当没有更多的动作是有可能， 1729-x 必须已经在黑板上的，因此，必须 使 1729- 2x， 。 。 。 1729-（q-1）x。然而， 1729-qx= r 不能在黑板上的，因为 r < x 且 x 则是定义为最小数目。唯一的解释是的 r = 0 ，这意味着 x | 1729 。由对成说法， x| 1390。因此，x 是一个 x 和 y 的公约数。1729 和 1390 仅有的公约数分别为 1 和 7，并问 题的前面部分得 x 不能是 1。因此，在游戏结束的时候，7 是在黑板上的。由于没有更多的动作 是有可能， 1729-7 ， 1729- 2∙7，。。。 ， 7 ， 0 ，都必须都在黑板上。所以每个 7 的正整数小于或等于 1729 在游戏结束的时候是在黑板上的。 (c)谁赢取？ 解：在黑板上由 1729/7 = 247 个数字，在游戏结束的时候。 因此，有 247− 2 =245 移动。 因 为您首先去，您也得到最后移动，在赢得游戏。 问题 7 证明以下定理。 定理： 如果 gcd (a， b) =1，那么 gcd (a+ b， a− b) =1 或 2。 解：因为 gcd (a， b) =1，那里存在整数 s 和 t，以便： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
现在，存在a+b和b的线性组合等于2！ (8+t)·(a+b)+(8-t)·(a-b)=2(s·a+t·b)=2 因此d(a+b,-b)至多为2，这蕴涵它是等于1成2， P诉文件使用"pdfFactory Pro”试用版本创建.fineprint,cn
现在，存在 a+b 和 a-b 的线性组合等于 2： 因此 gcd (a+ b， a− b)至多为 2，这蕴涵它是等于 1 或 2。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn