
问题月题集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