第13讲 抽屉原理
第13讲抽屉原理
把5个苹果放到4个抽屉中，必然有一个抽屉中至少有2个苹果，这是抽屉原理的通俗解释。一般地，我们将它表述为：
第一抽屉原理：把（mn＋1）个物体放入n个抽屉，其中必有一个抽屉中至少有（m＋1）个物体。
使用抽屉原理解题，关键是构造抽屉。一般说来，数的奇偶性、剩余类、数的分组、染色、线段与平面图形的划分等，都可作为构造抽屉的依据。
例1从1，2，3，…，100这100个数中任意挑出51个数来，证明在这51个数中，一定：
（1）有2个数互质；
（2）有2个数的差为50；
（3）有8个数，它们的最大公约数大于1。
证明：（1）将100个数分成50组：
{1，2}，{3，4}，…，{99，100}。
在选出的51个数中，必有2个数属于同一组，这一组中的2个数是两个相邻的整数，它们一定是互质的。
（2）将100个数分成50组：
{1，51}，{2，52}，…，{50，100}。
在选出的51个数中，必有2个数属于同一组，这一组的2个数的差为50。
（3）将100个数分成5组（一个数可以在不同的组内）：
第一组：2的倍数，即{2，4，…，100}；
第二组：3的倍数，即{3，6，…，99}；
第三组：5的倍数，即{5，10，…，100}；
第四组：7的倍数，即{7，14，…，98}；
第五组：1和大于7的质数即{1，11，13，…，97}。
第五组中有22个数，故选出的51个数至少有29个数在第一组到第四组中，根据抽屉原理，总有8个数在第一组到第四组的某一组中，这8个数的最大公约数大于1。
例2求证：可以找到一个各位数字都是4的自然数，它是1996的倍数。
证明：因1996÷4＝499，故只需证明可以找到一个各位数字都是1
的自然数，它是499的倍数就可以了。
得到500个余数r1，r2，…，r500。由于余数只能取0，1，2，…，499这499个值，所以根据抽屉原理，必有2个余数是相同的，这2个数的差就是499的倍数，这个差的前若干位是1，后若干位是0：11…100…0，又499和10是互质的，故它的前若干位由1组成的自然数是499的倍数，将它乘以4，就得到一个各位数字都是4的自然数，它是1996的倍数。
例3在一个礼堂中有99名学生，如果他们中的每个人都与其中的66人相识，那么可能出现这种情况：他们中的任何4人中都一定有2人不相识（假定相识是互相的）。
分析：注意到题中的说法“可能出现……”，说明题的结论并非是条件的必然结果，而仅仅是一种可能性，因此只需要设法构造出一种情况使之出现题目中所说的结论即可。
解：将礼堂中的99人记为a1，a2，…，a99，将99人分为3组：
（a1，a2，…，a33），（a34，a35，…，a66），（a67，a68，…，a99），将3组学生作为3个抽屉，分别记为A，B，C，并约定A中的学生所认识的66人只在B，C中，同时，B，C中的学生所认识的66人也只在A，C
和A，B中。如果出现这种局面，那么题目中所说情况就可能出现。
因为礼堂中任意4人可看做4个苹果，放入A，B，C三个抽屉中，必有2人在同一抽屉，即必有2人来自同一组，那么他们认识的人只在另2组中，因此他们两人不相识。
例4 如右图，分别标有数字1，2，…，8的滚珠两组，放在内外两个圆环上，开始时相对的滚珠所标数字都不相同。当两个圆环按不同方向转动时，必有某一时刻，内外两环中至少有两对数字相同的滚珠相对。
分析：此题中没有直接提供我们用以构造抽屉和苹果的数量关系，需要转换一下看问题的角度。
解：内外两环对转可看成一环静止，只有一个环转动。一个环转动一周后，每个滚珠都会有一次与标有相同数字的滚珠相对的局面出现，那么这种局面共要出现8次。将这8次局面看做苹果，再需构造出少于8个抽屉。
注意到一环每转动45°角就有一次滚珠相对的局面出现，转动一周共有8次滚珠相对的局面，而最初的8对滚珠所标数字都不相同，所以数字相同的滚珠相对的情况只出现在以后的7次转动中，将7次转动看做7个抽屉，8次相同数字滚珠相对的局面看做8个苹果，则至少有2次数字相对的局面出现在同一次转动中，即必有某一时刻，内外两环中至少有两对数字相同的滚珠相对。
例5有一个生产天平上用的铁盘的车间，由于工艺上的原因，只能控制盘的重量在指定的20克到20.1克之间。现在需要重量相差不超过0.005克的两只铁盘来装配一架天平，问：最少要生产多少个盘子，才能保证一定能从中挑出符合要求的两只盘子？
解：把20～20.1克之间的盘子依重量分成20组：
第1组：从20.000克到20.005克；
第2组：从20.005克到20.010克；
……
第20组：从20.095克到20.100克。
这样，只要有21个盘子，就一定可以从中找到两个盘子属于同一组，这2个盘子就符合要求。
例6 在圆周上放着100个筹码，其中有41个红的和59个蓝的。那么总可以找到两个红筹码，在它们之间刚好放有19个筹码，为什么？
分析：此题需要研究“红筹码”的放置情况，因而涉及到“苹果”的具体放置方法，由此我们可以在构造抽屉时，使每个抽屉中的相邻“苹果”之间有19个筹码。
解：依顺时针方向将筹码依次编上号码：1，2，…，100。然后依照以下规律将100个筹码分为20组：
（1，21，41，61，81）；
（2，22，42，62，82）；
……
（20，40，60，80，100）。
将41个红筹码看做苹果，放入以上20个抽屉中，因为41=2×20＋1，所以至少有一个抽屉中有2+1=3（个）苹果，也就是说必有一组5个筹码中有3个红色筹码，而每组的5个筹码在圆周上可看做两两等距，且每2个相邻筹码之间都有19个筹码，那么3个红色筹码中必有2个相邻（这将在下一个内容——第二抽屉原理中说明），即有2个红色筹码之间有19个筹码。
下面我们来考虑另外一种情况：若把5个苹果放到6个抽屉中，则必然有一个抽屉空着。这种情况一般可以表述为：
第二抽屉原理：把（mn-1）个物体放入n个抽屉，其中必有一个抽屉中至多有（m-1）个物体。
例7在例6中留有一个疑问，现改述如下：在圆周上放有5个筹码，其中有3个是同色的，那么这3个同色的筹码必有2个相邻。
分析：将这个问题加以转化：
如右图，将同色的3个筹码A，B，C置于圆周上，看是否能用另外2个筹码将其隔开。
解：如图，将同色的3个筹码放置在圆周上，将每2个筹码之间的间隔看做抽屉，将其余2个筹码看做苹果，将2个苹果放入3个抽屉中，则必有1个抽屉中没有苹果，即有2个同色筹码之间没有其它筹码，那么这2个筹码必相邻。
例8甲、乙二人为一个正方形的12条棱涂红和绿2种颜色。首先，甲任选3条棱并把它们涂上红色；然后，乙任选另外3条棱并涂上绿色；接着甲将剩下的6条棱都涂上红色。问：甲是否一定能将某一面的4条棱全部涂上红色？
解：不能。
如右图将12条棱分成四组：
第一组：{A1B1，B2B3，A3A4}，
第二组：{A2B2，B3B4，A4A1}，
第三组：{A3B3，B4B1，A1A2}，
第四组：{A4B4，B1B2，A2A3}。
无论甲第一次将哪3条棱涂红，由抽屉原理知四组中必有一组的3
条棱全未涂红，而乙只要将这组中的3条棱涂绿，甲就无法将某一面的4条棱全部涂红了。
下面我们讨论抽屉原理的一个变形——平均值原理。
我们知道n个数a1，a2，…，an的和与n的商是a1，a2，…，a n这n 个数的平均值。
平均值原理：如果n个数的平均值为a，那么其中至少有一个数不大于a，也至少有一个不小于a。
例9圆周上有2000个点，在其上任意地标上0，1，2，…，1999（每一点只标一个数，不同的点标上不同的数）。求证：必然存在一点，与它紧相邻的两个点和这点上所标的三个数之和不小于2999。
解：设圆周上各点的值依次是a1，a2，…，a2000，则其和
a1＋a2+…＋a2000=0+1+2+…+1999=1999000。
下面考虑一切相邻三数组之和：
（a1＋a2＋a3）+（a2＋a3＋a4）＋…＋（a1998+a1999＋a2000）＋（a1999
＋a2000＋a1）＋（a2000＋a1＋a2）
=3（a1＋a2＋…＋a2000）
＝3×1999000。
这2000组和中必至少有一组和大于或等于
但因每一个和都是整数，故有一组相邻三数之和不小于2999，亦即存在一个点，与它紧相邻的两点和这点上所标的三数之和不小于2999。
例10一家旅馆有90个房间，住有100名旅客，如果每次都恰有90名旅客同时回来，那么至少要准备多少把钥匙分给这100名旅客，才能使得每次客人回来时，每个客人都能用自己分到的钥匙打开一个房门住进去，并且避免发生两人同时住进一个房间？
解：如果钥匙数小于990，那么90个房间中至少有一个房间的钥匙数少
房间就打不开，因此90个人就无法按题述的条件住下来。
另一方面，990把钥匙已经足够了，这只要将90把不同的钥匙分给90个人，而其余的10名旅客，每人各90把钥匙（每个房间一把），那么任何90名旅客返回时，都能按要求住进房间。
最后，我们要指出，解决某些较复杂的问题时，往往要多次反复地运用抽屉原理，请看下面两道例题。
例11设有4×28的方格棋盘，将每一格涂上红、蓝、黄三种颜色中的任意一种。试证明：无论怎样涂法，至少存在一个四角同色的长方形。
证明：我们先考察第一行中28个小方格涂色情况，用三种颜色涂28个小方格，由抽屉原理知，至少有10个小方格是同色的，不妨设其为红色，还可设这10个小方格就在第一行的前10列。
下面考察第二、三、四行中前面10个小方格可能出现的涂色情况。这有两种可能：
（1）这三行中，至少有一行，其前面10个小方格中，至少有2个小方格是涂有红色的，那么这2个小方格和第一行中与其对应的2个小方格，便是一个长方形的四个角，这个长方形就是一个四角同是红色的长方形。
（2）这三行中每一行前面的10格中，都至多有一个红色的小方格，不妨设它们分别出现在前三列中，那么其余的3×7个小方格便只能涂上黄、蓝两种颜色了。
我们先考虑这个3×7的长方形的第一行。根据抽屉原理，至少有4个小方格是涂上同一颜色的，不妨设其为蓝色，且在第1至4列。
再考虑第二行的前四列，这时也有两种可能：
（1）这4格中，至少有2格被涂上蓝色，那么这2个涂上蓝色的小方格和第一行中与其对应的2个小方格便是一个长方形的四个角，这个长方形四角同是蓝色。
（2）这4格中，至多有1格被涂上蓝色，那么，至少有3格被涂上黄色。不妨设这3个小方格就在第二行的前面3格。
下面继续考虑第三行前面3格的情况。用蓝、黄两色涂3个小方格，由抽屉原理知，至少有2个方格是同色的，无论是同为蓝色或是同为黄色，都可以得到一个四角同色的长方形。
总之，对于各种可能的情况，都能找到一个四角同色的长方形。
例12 试卷上共有4道选择题，每题有3个可供选择的答案。一群学生参加考试，结果是对于其中任何3人，都有一道题目的答案互不相同。问：参加考试的学生最多有多少人？
解：设每题的三个选择分别为a，b，c。
（1）若参加考试的学生有10人，则由第二抽屉原理知，第一题答案分别为a，b，c的三组学生中，必有一组不超过3人。去掉这组学生，在余下的学生中，定有7人对第一题的答案只有两种。对于这7人关于第二题应用第二抽屉原理知，其中必可选出5人，他们关于第二题的答案只有两种可能。对于这5人关于第三题应用第二抽屉原理知，可以选出4人，他们关于第三题的答案只有两种可能。最后，对于这4人关于第四题应用第二抽屉原理知，必可选出3人，他们关于第四题的答案也只有两种。于是，对于这3人来说，没有一道题目的答案是互不相同的，这不符合题目的要求。可见，所求的最多人数不超过9人。
另一方面，若9个人的答案如下表所示，则每3人都至少有一个问题的答案互不相同。
所以，所求的最多人数为9人。
练习13
1.六（1）班有49名学生。数学王老师了解到在期中考试中该班英文成绩除3人外均在86分以上后就说：“我可以断定，本班同学至少有4人成绩相同。”请问王老师说得对吗？为什么？
2.现有64只乒乓球，18个乒乓球盒，每个盒子里最多可以放6只乒乓球，至少有几个乒乓球盒子里的乒乓球数目相同？
3.某校初二年级学生身高的厘米数都为整数，且都不大于160厘米，不小于150厘米。问：在至少多少个初二学生中一定能有4个人身高相同？
4.从1，2，…，100这100个数中任意选出51个数，证明在这51
个数中，一定：
（1）有两个数的和为101；
（2）有一个数是另一个数的倍数；
（3）有一个数或若干个数的和是51的倍数。
5.在3×7的方格表中，有11个白格，证明
（1）若仅含一个白格的列只有3列，则在其余的4列中每列都恰有两个白格；
（2）只有一个白格的列只有3列。
6.某个委员会开了40次会议，每次会议有10人出席。已知任何两个委员不会同时开两次或更多的会议。问：这个委员会的人数能够多于60人吗？为什么？
7.一个车间有一条生产流水线，由5台机器组成，只有每台机器都开动时，这条流水线才能工作。总共有8个工人在这条流水线上工作。在每一个工作日内，这些工人中只有5名到场。为了保证生产，要对这8名工人进行培训，每人学一种机器的操作方法称为一轮。问：最少要进行多少轮培训，才能使任意5个工人上班而流水线总能工作？
8.有9名数学家，每人至多能讲3种语言，每3人中至少有2人能通话。求证：在这9名中至少有3名用同一种语言通话。
练习13
1.对。解：因为49-3=3×（100-86+1）+1，即46=3×15+1，也就是
说，把从100分至86分的15个分数当做抽屉，49-3=46（人）的成绩当
做物体，根据第二抽屉原理，至少有4人的分数在同一抽屉中，即成绩相同。
2.4个。解：18个乒乓球盒，每个盒子里至多可以放6只乒乓球。为
使相同乒乓球个数的盒子尽可能少，可以这样放：先把盒子分成6份，每份有18÷6=3（只），分别在每一份的3个盒子中放入1只、2只、3只、4只、5只、6只乒乓球，即3个盒子中放了1只乒乓球，3个盒中放了2只乒乓球……3个盒子中放了6只乒乓球。这样，18个盒子中共放了乒乓球
（1+2+3+4+5+6）×3=63（只）。
把以上6种不同的放法当做抽屉，这样剩下64-63=1（只）乒乓球不管放入哪一个抽屉里的任何一个盒子里（除已放满6只乒乓球的抽屉外），都将使该盒子中的乒乓球数增加1只，这时与比该抽屉每盒乒乓数多1
的抽屉中的3个盒子里的乒乓球数相等。例如剩下的1只乒乓球放进原来有2只乒乓球的一个盒子里，该盒乒乓球就成了3只，再加上原来装有3只乒乓球的3个盒子，这样就有4个盒子里装有3个乒乓球。所以至少有4个乒乓球盒里的乒乓球数目相同。
3.34个。
解：把初二学生的身高厘米数作为抽屉，共有抽屉
160-150+1=11（个）。
根据抽屉原理，要保证有4个人身高相同，至少要有初二学生
3×11+1=34（个）。
4.证：（1）将100个数分成50组：
｛1，100｝，｛2，99｝，…，｛50，51｝。
在选出的51个数中，必有两数属于同一组，这一组的两数之和为101。
（2）将100个数分成10组：
｛1,2,4,8,16,32,64｝, ｛3,6,12,24,48,96｝,
｛5,10,20,40,80｝, ｛7,14,28,56｝,
｛9,18,36,72｝, ｛11,22,44,88｝,
｛13,26,52｝, ｛15,30,60｝,…,
｛49,98｝, ｛其余数｝。
其中第10组中有41个数。在选出的51个数中，第10组的41个数全部选中，还有10个数从前9组中选，必有两数属于同一组，这一组中的任意两个数，一个是另一个的倍数。
（3）将选出的51个数排成一列：
a1，a2，a3，…，a51。
考虑下面的51个和：
a1，a1+a2，a1+a2+a3，…，
a1+a2+a3+…+a51。
若这51个和中有一个是51的倍数，则结论显然成立；若这51个和中没有一个是51的倍数，则将它们除以51，余数只能是1，2，…，50中的一个，故必然有两个的余数是相同的，这两个和的差是51的倍数，而这个差显然是这51个数（a1，a2，a3，…，a51）中的一个数或若干个数的和。
5.证：（1）在其余4列中如有一列含有3个白格，则剩下的5个白格要放入3列中，将3列表格看做3个抽屉，5个白格看做5个苹果，根据第二抽屉原理，5（=2×3-1）个苹果放入3个抽屉，则必有1个抽屉至多只有（2-1）个苹果，即必有1列只含1个白格，也就是说除了原来3列只含一个白格外还有1列含1个白格，这与题设只有1个白格的列只有3列矛盾。所以不会有1列有3个白格，当然也不能再有1列只有1个白格。推知其余4列每列恰好有2个白格。
（2）假设只含1个白格的列有2列，那么剩下的9个白格要放入5列中，而9=2×5-1，由第二抽屉原理知，必有1列至多只有2-1=1（个）白格，与假设只有2列每列只1个白格矛盾。所以只有1个白格的列至少有3列。
6.能。
解：开会的“人次”有40×10=400（人次）。设委员人数为N，将“人次”看做苹果，以委员人数作为抽屉。
若N≤60，则由抽屉原理知至少有一个委员开了7次（或更多次）会。但由已知条件知没有一个人与这位委员同开过两次（或更多次）的会，故
他所参加的每一次会的另外9个人是不相同的，从而至少有7×9=63（个）委员，这与N≤60的假定矛盾。所以，N应大于60。
7.20轮。
解：如果培训的总轮数少于20，那么在每一台机器上可进行工作的工人
果这3个工人某一天都没有到车间来，那么这台机器就不能开动，整个流水线就不能工作。故培训的总轮数不能少于20。
另一方面，只要进行20轮培训就够了。对3名工人进行全能性培训，训练他们会开每一台机器；而对其余5名工人，每人只培训一轮，让他们每人能开动一台机器。这个方案实施后，不论哪5名工人上班，流水线总能工作。
8.证：以平面上9个点A1，A2，…，A9表示9个数学家，如果两人能通话，就把表示他们的两点联线，并涂上一种颜色（不同的语言涂上不同颜色）。此时有两种情况：
（1）9点中有任意2点都有联线，并涂了相应的颜色。于是从某一点A1出发，分别与A2，A3，…，A9联线，又据题意，每人至多能讲3种语言，因此A1A2，A1A3，…，A1A9中至多只能涂3种不同的颜色，由抽屉原理知，这8条线段中至少有2条同色的线段。不妨设A1A2与A1A3
是同色线段，因此A1，A2，A3这3点表示的3名数学家可用同一种语言通话。
（2）9点中至少有2点不联线，不妨设是A1与A2不联线。由于每3人中至少有两人能通话，因此从A1与A2出发至少有7条联线。再由抽屉原理知，其中必有4条联线从A1或A2出发。不妨设从A1出发，又因
A1至多能讲3种语言，所以这4条联线中，至少有2条联线是同色的。若A1A3与A1A4同色，则A1，A3，A4这3点表示的3名数学家可用同一种语言通话。
第31讲容斥原理
第31讲容斥原理 例题与方法 例1 在1～100的自然数中，不能被3也不能被5整除的数有多少个？ 例2 某班有52人，其中会下棋的有48人，会画画的有37人，会跳舞的有39人，这三项都会的至少有几人？ 例3 100名学生中，每人至少懂一种外语，其中75人懂法语，83人懂英语，65人懂日语，懂三种语言的有50人，懂两种外语的有多少人？ 例4 在1～143这143个自然数中，与143互质的自然数共有多少个？ 例5 某班学生参加语文、数学、英语三科考试，语文、数学、英语都得满分的分别有21人、19人、20人。语文、数学都得满分的有9人；数学、英语都得满分的有7人；语文、英语都得满分的有8人；另有5人三科都未得满分。这个班最多能有多少人？ 思考与练习 1．某班有学生46名，其中爱好音乐的有17人，爱好美术的有14人，既爱好音乐又爱好美术的有5人。问：两样都不爱好的有多少人？ 2．分母是105的最简真分数共有多少个？ 3．一个家电维修站有80%工人精通修彩电，有70%的人精通修空调，10%的人两项不熟悉。问：两项都精通的人占白分之几？ 4．在1～100的自然数中，既不能被5整除也不能被9整除的数的和是多少？ 5．在1～200的自然数中，能被2整除，或能被3整除，或能被5整除的数共有多少个？ 6．在100名学生中，爱好音乐的有56人，爱好体育的有75人，那么既爱好音乐又爱好体育的最少有多少人，最多有多少人？ 7．64人订A、B、C三种杂志，订A杂志的有28人，订B杂志的有41人，订C杂志的有20人，订A、B两种杂志的有10人，订B、C两种杂志的有12人，订A、C两种杂志的有12人。三种杂志都订的有多少人？ 8．有100位旅客，其中有10人既不懂英语又不懂俄语，有75人懂英语，有83人懂俄语，那么这100位旅客中既懂英语懂俄语的有多少人？
小学数学 位值原理.教师版
5-7-1.位值原理 教学目标 1.利用位值原理的定义进行拆分 2.巧用方程解位值原理的题 知识点拨 位值原理 当我们把物体同数相联系的过程中，会碰到的数越来越大，如果这种联系过程中，只用我们的手指头，那么到了“十”这个数，我们就无法数下去了，即使象古代墨西哥尤里卡坦的玛雅人把脚趾也用上，只不过能数二十。我们显然知道，数是可以无穷无尽地写下去的，因此，我们必须把数的概念从实物的世界中解放出来，抽象地研究如何表示它们，如何对它们进行运算。这就涉及到了记数，记数时，同一个数字由于所在位置的不同，表示的数值也不同。既是说，一个数字除了本身的值以外，还有一个“位置值”。例如，用符号555表示五百五十五时，这三个数字具有相同的数值五，但由于位置不同，因此具有不同的位置值。最右边的五表示五个一，最左边的五表示五个百，中间的五表示五个十。但是在奥数中位值问题就远远没有这么简单了，现在就将解位值的三大法宝给同学们。希望同学们在做题中认真体会。 1.位值原理的定义：同一个数字，由于它在所写的数里的位置不同，所表示的数值也不同。也就是说，每一个数字除了有自身的一个值外，还有一个“位置值”。例如“2”,写在个位上，就表示2个一，写在百位上，就表示2个百，这种数字和数位结合起来表示数的原则，称为写数的位值原理。 2.位值原理的表达形式：以六位数为例：abcdef a×100000+b×10000+c×1000+d×100+e×10+f。 3.解位值一共有三大法宝：（1）最简单的应用解数字谜的方法列竖式 （2）利用十进制的展开形式，列等式解答 （3）把整个数字整体的考虑设为x，列方程解答 例题精讲 模块一、简单的位值原理拆分 【例1】一个两位数，加上它的个位数字的9倍，恰好等于100。这个两位数的各位数字的和是。【考点】简单的位值原理拆分【难度】2星【题型】填空 【关键词】希望杯，4年级，初赛，7题，六年级，初赛，第8题，5分 【解析】这个两位数，加上它的个位数字的9倍，恰好等于100，也就是说，十位数字的10倍加上个位数字的10倍等于100，所以十位数字加个位数字等于100÷10＝10。 【答案】10 【例2】学而思的李老师比张老师大18岁，有意思的是，如果把李老师的年龄颠倒过来正好是张老师的年龄，求李老师和张老师的年龄和最少是________？（注：老师年龄都在20岁以上） 【考点】简单的位值原理拆分【难度】3星【题型】填空 【关键词】学而思杯，4年级，第5题
第八讲-组合数学
第八讲 组合数学 组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开 例1．圆周上有800个点，依顺时针方向标号为1,2,…,800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k 号点染成了红色，则可依顺时针方向转过k 个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？ 解：易见，第k 号点能被染红的充要条件是 ?j ∈N *?{0}，使得a 0?2j ≡k (mod800)，1≤k ≤800 ① 这里a 0是最初染的点的号码，为求最大值，不妨令a 0=1.即2j ≡k (mod25×52). 当j=0,1,2,3,4时，k 分别为1,2,4,8,16，又由于2模25的阶20)2(25=δ，因此，当j ≥5时 2j+20-2j =2j (220-1)≡0(mod 800), 而对?k<20,k ∈N *，及j ≥5,j ∈N *，由于25+(2k -1)，所以 2j+k -2j =2j (2k -1)不为800的倍数. 所以，共存在5+20=25个k ，满足①式。 注：本题解法不止一种，但利用些同余理论，可使解法简洁许多. 例2．集合X 的覆盖是指X 的一族互不相同的非空子集A 1、A 2、…、A k ，它们的并集A 1∪A 2∪…∪A k =X ，现有集合X={1,2,…,n}，若不考虑A 1, A 2,…, A k 的顺序，试求X 的覆盖有多少个？ 解：首先，X 的非空子集共有2n -1个，它们共组成了n 2 1 2--1个非空子集族.其次， 这些子集族中，不合某一元素i 的非空子集组成的非空子集族有( ) n 121 21---个；不含两 个元素的子集组成的族有( ) n 2 2 1 21---个；依次类推，则由容斥原理，X 的覆盖共有 ()() --+--------)12 ()12 ()12 (1 22 1 21 1 221n n n n n =())12()1(1 2 1 ---=-∑n n j n j j 个. 注：有些组合计数问题直接计数较难，但从反面考虑简洁明了.
六年级数学培优之整除和位值原理
第九讲 整除和位值原理 例1：证明：当a c >时，abc cba -必是9的倍数。 例2：有一个两位数，把数码1加在它的前面可以得到一个三位数，加在它的后面也可以得到一个三位数，这两个三位数相差666。求原来的两位数。 例3： a ，b ，c 是1～9中的三个不同的数码，用它们组成的六个没有重复数字的三位数之和是（a+b+c ）的多少倍？ 例4：用2，8，7三张数字卡片可以组成若干个不同的三位数，所有这些三位数的平均值是多少？ 例5：一个两位数，各位数字的和的5倍比原数大6，求这个两位数。 例6：将一个三位数的数字重新排列，在所得到的三位数中，用最大的减去最小的，正好等于原来的三位数，求原来的三位数。 A 1.一个自然数与13的和是5的倍数，与13的差是6的倍数，则满足条件的最小自然数是 ． 2.有三个正整数a 、b 、c 其中a 与b 互质且b 与c 也互质，给出下面四个判断：①(a+c) 2不能被b 整除，②a 2+c 2不能被b 整除：③(a+b)2不能被c 整除；④a 2+b 2不能被c 整除，其 中，不正确的判断有( )． A ．4个 B ．3个 C 2个 D ．1个 3.已知7位数61287xy 是72的倍数，求出所有的符合条件的7位数． 4.(1)一个自然数N 被10除余9，被9除余8，被8除余7，被7除余6，被6除余5，被5除余4，被3除余2，被2除余1，则N 的最小值是 ．
(北京市竞赛题) (2)若1059、1417、2312分别被自然数x 除时，所得的余数都是y ，则x —y 的值等于( )． A ．15 B ．1 C ．164 D ．174 (“五羊杯”竞赛题) (3)设N= 个 1990111，试问N 被7除余几?并证明你的结论． (安徽省竞赛题) 5.盒中原有7个球，一位魔术师从中任取几个球，把每一个小球都变成了7个小球，将其放回盒中，他又从盒中任取一些小球，把每一个小球又都变成了7个小球后放回盒中，如此进行，到某一时刻魔术师停止取球变魔术时，盒中球的总数可能是( ) A ．1990个 B ．1991个 C 1992个 D ．1993个 B 6.在100以内同时被2、3、5整除的正整数有多少个? 7.某商场向顾客发放9999张购物券，每张购物券上印有一个四位数的号码，从0001到9999号，如果号码的前两位数字之和等于后两位数字之和，则称这张购物券为“幸运券”．证明：这个商场所发放的购物券中，所有的幸运券的号码之和能被101整除． 8.写出都是合数的13个连续自然数． 9.已知定由“若大于3的三个质数a 、b 、c 满足关系式20+5b=c ，则a+b+c 是整数n 的倍数”．试问：这个定理中的整数n 的最大可能值是多少?请证明你的结论． 10.一个正整数N 的各位数字不全相等，如果将N 的各位数字重新排列，必可得到一个最大数和一个最小数，若最大数与最小数的差正好等于原来的数N ，则称N 为“新生数”，试求所有的三位“新生数”． 11.设N 是所求的三位“新生数”，它的各位数字分别为a 、b 、c (a 、b 、c 不全相等)，将其各位数字重新排列后，连同原数共得6个三位数：cba cab bca bac acb abc ,,,,,，不妨设其中的最大数为abc ，则最小数为cba ．由“新生数”的定义，得N=abc —cba =(100a+l0b+c)一(100c+l0b+d)=99(a —c)． C 12.从左向右将编号为1至2002号的2002个同学排成一行，从左向右从1到11报数，报到11的同学原地不动，其余同学出列；然后，留下的同学再从左向右从1到11报数，报到11的同学留下，其余同学出列；留下的同学再从左向左从1到11地报数，报到11的同学留下，其余同学出列．问最后留下的同学有多少?他们的编号是几号? 13.在一种游戏中，魔术师请一个人随意想一个三位数cba cab bca bac abc 、、、、的和N ，把N 告诉魔术师，于是魔术师就能说出这个人所想的数abc ．现在设N=3194，请你做魔术师，
小学四年级奥数 第13讲：位值原理
位值原理 叁仟陆佰伍拾捌 3 6 5 8 加油站 位值原理的定义： 同一个数字，由于它在所写的数里的位置不同，所表示 的数值也不同.也就是说，每一个数字除了有自身的一个值外， 还有一个“位置值”.例如“2”，写在个位上，就表示2个一， 写在百位上，就表示2个百，这种数字和数位结合起来表示数
的原则，称为写数的位值原理. 【例1】(★) 填空: ⑴ 123＝1个（ ）＋2个（ ）＋3个（ ） ⑵234＝（ ）个100＋（ ）个10＋（ ）个1 ⑶24＝2×（ ）＋4×（ ） 【例2】(★ ★) : ⑴ 30300 3 3 ⑵ 22030 2 2 3 ⑷657＝（ ）×100＋（ ）×10＋（ ）×1 2 3 ⑸ （ ）＝5×100＋7×10＋9×1 ⑹ 23＋45＝（ ）×10＋（ ）×1 ⑺ 234＋321＝（ ）×100＋（ ）×10＋（ ）×1 ＝（ ）×111 ⑶ abc 100 10+ 1 ⑷ abcd a b c d ⑸ 1
【例3】（★★★）【例5】(★★★)(希望杯五年级一试试题） ⑴ 三位数abc比三位数cba小99，若a,b,c彼此不 同，则abc最大是_____。 ⑵a b a b 98790807 【例6】(★★★★) 【例4】(★★★) 计算：(123456＋234561＋345612＋456123＋561234＋612345)÷7 从1～9九个数字中取出三个，用这三个数可组成六个不同的三 位 数.若这六个三位数之和是3330，则这六个三位数中最小至少是 多 少？最大的至多是多少？ 【例7】(★★★★★)(希望杯四年级二试试题) 本讲总结 数abcd，abc，ab，a依次表示四位数、三位数、 两位数及一位abcd abc ab a 1787，那么满足条件的是多少？ abcd a c=a c 重要应用： ①计算——分位计算 ②代数化表示——分类讨论
初一数学竞赛系列讲座容斥原理
初一数学竞赛系列讲座 容斥原理 集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#
初一数学竞赛系列讲座(15) 容斥原理 一、 知识要点 1、容斥原理 在计数时，常常遇到这样的情况，作合并运算时会把重复的部分多算，需要减去；作排除运算时会把重复部分多减，需要加上，这就是容斥原理。它的基本形式是： 记A 、B 是两个集合，属于集合A 的东西有A 个，属于集合B 的东西有B 个，既属于集合A 又属于集合B 的东西记为B A ，有B A 个；属于集合A 或属于集合B 的东西记为B A ，有B A 个，则有：B A =A +B -B A 容斥原理可以用一个直观的图形来解释。 如图， 左圆表示集合A ，右圆表示集合B ，两圆的公共部分表示B A ，两圆合起来的部分表示B A ， 由图可知：B A =A +B -B A 容斥原理又被称作包含排除原理或逐步淘汰原则。 二、 例题精讲 例1 在1到200的整数中，既不能被2整除，又不能被3整除的整数有多少个 分析：根据容斥原理，应是200减去能被2整除的整数个数，减去能被3整除的整数个数，还要加上既能被2整除又能被3整除，即能被6整除的整数个数。 解：在1到200的整数中，能被2整除的整数个数为：2?1，2?2，…，2?100，共100个； 在1到200的整数中，能被3整除的整数个数为：3?1，3?2，…，3?66，共66个； 在1到200的整数中，既能被2整除又能被3整除，即能被6整除的整数个数为： 6?1， 6?2，…，6?33，共33个； 所以，在1到200的整数中，既不能被2整除，又不能被3整除的整数个数为：
第十讲 容斥原理小学五年级奥数
點算的奧秘：容斥原理基本公式 「容斥原理」(Principle of Inclusion and Exclusion)(亦作「排容原理」)是「點算組合學」中的一條重要原理。但凡略為複雜、包含多種限制條件的點算問題，都要用到這條原理。現在首先從一個點算問題說起。 例題1：設某班每名學生都要選修至少一種外語，其中選修英語的學生人數為25，選修法語的學生人數為18，選修德語的學生人數為20，同時選修英語和法語的學生人數為8，同時選修英語和德語的學生人數為13 ，同時選修法語和德語的學生人數為6，而同時選修上述三種外語的學生人數則為3，問該班共有多少名學生？ 答1：我們可以把上述問題表達為下圖： 其中紅色、綠色和藍色圓圈分別代表選修英語、法語和德語的學生。根據三個圓圈之間的交叉關係，可把上圖分為七個區域，分別標以A至G七個字母。如果我們用這七個字母分別代表各字母所在區域的學生人數，那麼根據題意，我們有以下七條等式：(1) A+D+E+G = 25；(2) B+D+F+G = 18；(3) C+E+F+G = 20；(4) D+G = 8； (5) E+G = 13；(6) F+G = 6；(7) G = 3。現在我們要求的是A+B+C+D+E+F+G。如何利用以上資料求得答案？ 把頭三條等式加起來，我們得到A+B+C+2D+2E+2F+3G = 63。可是這結果包含了多餘的D、E、F和G，必須設法把多餘的部分減去。由於等式(4)－(6)各有一個D、E和F，若從上述結果減去這三條等式，便可以把多餘的D、E和 F減去，得A+B+C+D+E+F = 36。可是這麼一來，本來重覆重現的G卻變被完全減去了，所以最後還得把等式(7)加上去，得最終結果為A+B+C+D+E+F+G = 39，即該班共有39名學生。□ 在以上例題中，給定的資料是三個集合的元素個數以及這些集合之間的交集的元素個數。在該題的解答中，我們交替加上及減去這些給定的資料。如果我們用 S 1、S 2 和S 3 分別代表選修英語、法語和德語學生的集合，那麼我們要求的答案就 是|S 1∪ S 2 ∪ S 3 |，而該題的解答則可以重新表達為
升第八讲容斥原理之重叠问题
第八讲：容斥原理之重叠问题 导入 文氏图■■■■■■■■■■■■■■■ 文氏图，也叫维恩图”是由英国著名数学家Venn发明的. 维恩（公元1834 年8月4日「公元1923 年4月4日）十九世纪英国著名的数学家和哲学家，生于英国赫尔.他1883 年获得理学博士学位，同年被选为英国皇家学会会员. 维恩最主要的成就是系统解释并发展了几何表示的方法，也就是发明了文氏图.■他作出一系列 ? 简单闭曲线（圆或更复杂的图形），将平面分为许多间隔.利用这种图表，维恩阐明了演绎推理的基本原 理.为了进一步明确起见，他还引入了一些数学难题作为实例.虽然在维恩之前， 莱布尼茨（Leibniz ）已系统地运用过这类逻辑图，但今天这种逻辑图仍称作维恩图”另外, 维 恩在概率论和逻辑学方面也有很大贡献，他的著作一一《机会逻辑》和《符号逻辑》，在19 世纪末20 世纪初曾享有很高的声誉. 除了数学以外，维恩还有一项较为特别的技能一一制作机器.他曾制作过一部板球发球机， 当澳洲板球队在1909 年到访剑桥大学时，维恩的机器依然运作正常，并使他们其中一位成员打空四次. 什么是容斥原理? 这一讲我们主要学习和“包含”与“排除”有关的问题，这样的问题在生活中就有不少，比如吃瓜子.我们说吃掉了一斤瓜子，指的是带壳的瓜子，并非真的吃到肚子里一斤，因为这一斤中还“包含”着瓜子壳.如果要计算到底吃了多少，最简单的方法就是称一称瓜子壳，用原来的一斤“排除”掉瓜子壳的重量.瓜子的例子相对简单，一斤瓜子里一部分是瓜子仁，另一部分就是瓜子壳，两者各不相关.但本讲要学习的包含与排除问题要复杂一些，各部分之间会有重叠. 比如一个办公室中每个人都至少爱喝茶或咖啡中的一种，已知有7个人爱喝茶，10个人爱喝咖啡，那能不能就说办公室里有17 个人呢？显然不能，因为可能有一些人既爱喝茶也爱 喝咖啡，如果直接将喝茶的人数和喝咖啡的人数相加，会把既爱喝茶又爱喝咖啡的人计算2 次，计算人数的时候要把这一部分减去才行. 比如，如果有3个人既爱喝茶又爱喝咖啡，那总的人数就应该是7 + 10 - 3 = 14 人.
4升5-8第八讲：容斥原理之重叠问题
第八讲：容斥原理之重叠问题 一、导入 文氏图 文氏图，也叫“维恩图”，是由英国著名数学家 Venn 发明的． 维恩（公元 1834 年 8 月 4 日─公元 1923 年 4 月 4 日）十九世纪英国著名的数学家和哲学家，生于英国赫尔．他 1883 年获得理学博士学位，同年被选为英国皇家学会会员． 维恩最主要的成就是系统解释并发展了几何表示的方法，也就是发明了文氏图．他作出一系列简单闭曲线（圆或更复杂的图形），将平面分为许多间隔．利用这种图表，维恩阐明了演绎推理的基本原理．为了进一步明确起见，他还引入了一些数学难题作为实例．虽然在维恩之前， 莱布尼茨（Leibniz）已系统地运用过这类逻辑图，但今天这种逻辑图仍称作“维恩图”另外，维恩在概率论和逻辑学方面也有很大贡献，他的著作——《机会逻辑》和《符号逻辑》，在 19 世纪末 20 世纪初曾享有很高的声誉． 除了数学以外，维恩还有一项较为特别的技能——制作机器．他曾制作过一部板球发球机，当澳洲板球队在 1909 年到访剑桥大学时，维恩的机器依然运作正常，并使他们其中一位成员打空四次． 什么是容斥原理？ 这一讲我们主要学习和“包含”与“排除”有关的问题，这样的问题在生活中就有不少， 比如吃瓜子．我们说吃掉了一斤瓜子，指的是带壳的瓜子，并非真的吃到肚子里一斤，因为这一斤中还“包含”着瓜子壳．如果要计算到底吃了多少，最简单的方法就是称一称瓜子壳，用原来的一斤“排除”掉瓜子壳的重量．瓜子的例子相对简单，一斤瓜子里一部分是瓜子仁，另一部分就是瓜子壳，两者各不相关．但本讲要学习的包含与排除问题要复杂一些，各部分之间会有重叠． 比如一个办公室中每个人都至少爱喝茶或咖啡中的一种，已知有 7 个人爱喝茶，10 个人爱喝咖啡，那能不能就说办公室里有 17 个人呢？显然不能，因为可能有一些人既爱喝茶也爱喝咖啡，如果直接将喝茶的人数和喝咖啡的人数相加，会把既爱喝茶又爱喝咖啡的人计算 2 次，计算人数的时候要把这一部分减去才行． 比如，如果有 3 个人既爱喝茶又爱喝咖啡，那总的人数就应该是 7 + 10 ? 3 = 14 人．
位值原理教案教学文案
位值原理教案
位值原理 知识要点 位值原理的定义：同一个数字，由于它在所写的数里的位置不同，所表示的数值也不同。也就是说，每一个数字除了有自身的一个值外，还有一个“位置值”。例如“2”,写在个位上，就表示2个一，写在百位上，就表示2个百，这种数字和数位结合起来表示数的原则，称为写数的位值原理。 位值原理的表达形式：以六位数为例：abcdef a×100000+b×10000+c×1000+d×100+e×10+f。 例题讲解 【例 1】某三位数abc和它的反序数cba的差被99除，商等于______与______的差； 【巩固】ab与ba的差被9除，商等于______与______的差； 【巩固】ab与ba的和被11除，商等于______与______的和。
【例 2】(美国小学数学奥林匹克)把一个两位数的十位与个位上的数字加以交换，得到一个新的两位数．如果原来的两位数和交换后的新的两位数 的差是45，试求这样的两位数中最大的是多少？ 【巩固】将一个四位数的数字顺序颠倒过来，得到一个新的四位数(这个数也叫原数的反序数)，新数比原数大8802．求原来的四位数． 【巩固】如果一个自然数的各个数码之积加上各个数码之和，正好等于这个自然数，我们就称这个自然数为“巧数”。例如，99就是一个巧数，因为9 ×9＋(9＋9)＝99。可以证明，所有的巧数都是两位数。请你写出所有 的巧数。
【例 3】 (第五届希望杯培训试题)有3个不同的数字，用它们组成6个不同的三位数，如果这6个三位数的和是1554，那么这3个数字分别是多 少？ 【巩固】(迎春杯决赛)有三个数字能组成6个不同的三位数，这6个三位数的和是2886，求所有这样的6个三位数中最小的三位数． 【巩固】用1，9，7三张数字卡片可以组成若干个不同的三位数，所有这些三位数的平均值是多少？ 【巩固】从1～9九个数字中取出三个，用这三个数可组成六个不同的三位数。 若这六个三位数之和是3330，则这六个三位数中最小的可能是几？最 大的可能是几？
第6讲 容斥原理
第六讲 容斥原理 在一些计数问题中，经常遇到有关集合元素个数的计算。我们用|A |表示有限集A 的元素的个数。在两个集合的研究中，已经知道，求两个集合并集的元素个数，不能简单地把两个集合的元素个数相加，而要从两根集合的个数之中减去重复计算的元素个数，用式子可以表示成 |A ∪B |=|A |+|B |–|A ∩B |。 我们称这一公式为包含与排除原理，简称为容斥原理。 包含与排除原理|告诉我们，要计算两个集合A 、B 的并集A ∪B 的元素个数，可以分一下两步进行： 第一步：分别计算集合A 、B 的元素个数，然后加起来。即先求|A |+|B |（意思是把A 、B 的一切元素都“包含”进来，加在一起）； 第二步“从上面的和中减去交集的元素的个数，即减去|A ∩B |（意思是“排除”了重复计算的元素的个数）。 例1．求不超过20的正整数中是2的倍数或3的倍数的数共有多少？ 解：设I ={1、2、3、…、19、20}，A ={I 中2的倍数}，B ={I 中3的倍数}。 显然题目中要求计算并集A ∪B 的元素个数，即求|A ∪B |。 我们知道A ={2、4、6、……、20}，所以|A |=10， B ={3、6、9、12、15、18}，|B |=6。 A ∩ B ={I 中既是2的倍数又是3的倍数}={6、12、18}，所以|A ∩B |=3， 根据容斥原理有|A ∪B |=|A |+|B |–|A ∩B |=10+6–3=13. 答：所求的数共有13个。 此题可以直观地用图表示如下： 例2．某班统计考试成绩，数学得90分以上的有25人，语文得90分以上的有21人，两科中至少有一科在90分以上的有38人，问两科都在90分以上的有多少人？ 解：设A ={数学在90分以上的学生}，B ={语文在90分以上的学生}， 由题意知|A |=25，|B |=21。 A ∪ B ={数学、语文至少一科在90分以上的学生}，|A ∪B |=38。 A ∩B ={数学、语文都在90分以上的学生}， 由容斥原理知|A ∪B |=|A |+|B |–|A ∩B |， 所以|A ∩B |=|A |+|B |–|A ∪B |=25+21–38=8。 答：两科都在90分以上的有8人。 画图分析一下： 15 9320 18 16141210 8 642B A
五年级奥数位值原理
位值原理 知识框架 当我们把物体同数相联系的过程中，会碰到的数越来越大，如果这种联系过程中，只用我们的手指头，那么到了“十”这个数，我们就无法数下去了，即使像古代墨西哥尤里卡坦的玛雅人把脚趾也用上，只不过能数二十.我们显然知道，数是可以无穷无尽地写下去的，因此，我们必须把数的概念从实物的世界中解放出来，抽象地研究如何表示它们，如何对它们进行运算.这就涉及到了记数，记数时，同一个数字由于所在位置的不同，表示的数值也不同.既是说，一个数字除了本身的值以外，还有一个“位置值”.例如，用符号555表示五百五十五时，这三个数字具有相同的数值五，但由于位置不同，因此具有不同的位置值.最右边的五表示五个一，最左边的五表示五个百，中间的五表示五个十.但是在奥数中位值问题就远远没有这么简单了，现在就将解位值的三大法宝给同学们.希望同学们在做题中认真体会. 1.位值原理的定义：同一个数字，由于它在所写的数里的位置不同，所表示的数值也不同.也就是说，每一个数字除了有自身的一个值外，还有一个“位置值”.例如“2”,写在个位上，就表示2个一，写在百位上，就表示2个百，这种数字和数位结合起来表示数的原则，称为写数的位值原理. 2.位值原理的表达形式：以六位数为例：abcdef a×100000+b×10000+c×1000+d×100+e×10+f. 3.解位值一共有三大法宝： （1）最简单的应用解数字谜的方法列竖式 （2）利用十进制的展开形式，列等式解答 （3）把整个数字整体的考虑设为x，列方程解答 例题精讲 知识点一：位值原理的认识 【例 1】填空：
365= ×100+ ×10+ ×1 365=36×+5× =2×+3×＋a×+b×=203 +× 【例 2】ab与ba的和被11除，商等于______与______的和。 【例 3】把一个两位数的个位数字与其十位数字交换后得到一个新数，它与原来数加起来的和恰好是121，这个两位数的数字和是多少？ 【巩固】把一个两位数的十位与个位上的数字加以交换，得到一个新的两位数．如果原来的两位数和交换后的新的两位数的差是45，试求这样的两位数中最大的是多少？ 【例 4】（1）用数字1、2、3各一个可以组成三位数，所有这样的三位数之和是多少？这个和是三位数的数字和的多少倍？ （2）有三个不同的数字，用它们组成六个不同的三位数，如果这六个三位数的和是1554，那么这 三个数字分别是多少？ 【巩固】从1-9这九个数字中取出3个，用这三个数字可以组成6个不同的三位数，若这六个三位数之和是2442，则这三个数字的和是多少？
第八讲容斥原理
第八讲容斥原理 在一些计数问题中，经常遇到有关集合元素个数的计算。我们用|A|表示有限集A的元素个数。在并集的讨论中，已经知道，求两个集合并集的元素的个数，不能简单地把两个集合的元素个数相加，而要从两个集合个数之和中减去重复计算的元素个数，即减去交集的元素个数，用式子可表示成 |A∪B|=|A|+|B|-|A∩B| 我们称这一公式为包含与排除原理，简称容斥原理。 包含与排除原理告诉我们，要计算两个集合A、B的并集A∪B的元素的个数，可分以下两步进行： 第一步分别计算集合A、B的元素个数，然后加起来，即先求|A|+|B|（意思是把A、B的一切元素都“包含”进来，加在一起）； 第二步从上面的和中减去交集的元素个数，即减去|A∩B|（意思是“排除”了重复计算的元素个数）。 例1 求不超过20的正整数中是2的数倍或3的倍数的数共有多少个。分析与解：设I=｛1，2，3，…，19，20｝，A=｛I中2的倍数｝，B=｛I 中3的倍数｝。 显然，题目要求计算并集|A∪B|的元素个数，即求|A∪B|。 易知， A=｛2，4，6，…，18，20｝， 共有10个元素，即|A|=10， B=｛3，6，9，12，15，18｝， 共有6个元素，即|B|=6。 A∩B=｛I中既是2的倍数又是3的倍数｝ =｛6，12，18｝ 共有3个元素，即|A∩B|=3，所以 |A∪B|=|A|+|B|-|A∩B| =10+6-3=13 答：所求的数共有13个。 此题可直观地图示如下： 图8-1中，A表示不超过20的正整数中2的倍数的集合。B表示不超过20的正整数中3的倍数的集合。在不超过20的正整数中既是2的倍数又是3的倍数的数有6，12，18，即A∩B中的数。 例2 某班统计考试成绩，数学得90分上的有25人；语文得90分以上的有21人；两科中至少有一科在90以上有38人。问两科都在90分以上的有多少人？（1985年初一迎春杯数学竞赛试题） 解：设A=｛数学成绩90分以上的学生）， B=｛语文成绩90分以上的学生｝。
四年级容斥原理
四年级名校第四讲容斥原理 教学目标： 1掌握容斥原理的基本解题方法。 2能简单的画出容斥原理的图。 3培养学生的逻辑思维能力。 教学重点 用画图的方法去解容斥原理。 教学难点 在做较复杂的容斥原理的题的时，如何用画图的方法去解答。 教学过程： 导入： 在我们日常生活中经常会碰到重复的时候，比如我们的爱好。像老师既喜欢做数学题也喜欢看小说。但是可能有些人就只喜欢做数学题，也可能只喜欢看小说，或者又喜欢看小说又喜欢看电视。引导学生说说自己的爱好。其实这个东西也包含了我们数学中的知识。今天我们就来学习与之有关的容斥原理。（出示课题） 新授： 例1两个面积是16平方厘米的正方形摆在桌面上，他们盖住的面积有32平方厘米吗？如果充电的部分是4平方厘米，则他们盖住的面积是多少平方厘米？ T：这2个正方形的面积和是2个16平方厘米就是32厘米，但是中间有盖住的部分，那么他们的总面积可能有32厘米么？因为有盖住的部分所以不可能。 T：接下来我们再来看下面的问题，如果盖住的部分是4平方厘米。我们来看一看盖住的部分是4平方厘米，是哪一部分是4平方厘米。我们来看一看如果我把2个正方形的面积总和都算出来这个重复的部分的4平方厘米我算了几次？2次。 T：事实上如果我们要计算盖住的面积那么我们重复的部分算几次就够了呢？1次，多算了依次怎么办？减掉就可以了。16＋16－4＝28（平方厘米） 练习：演练一 例2实验小学四（1）班同学参加语文和数学兴趣小组，参加语文兴趣小组的有25人，参加数学兴趣小组的有34人，其中有15人两个小组都参加。这个班共有多少人参加了语文或数学兴趣小组？ T：我们来观察一下题目，这里面有没有例1时重复的部分呢？有，就是2个兴趣小组都参加的人。 T：那我们是不是可以画一个跟例差不多的图呢？中间的部分就是重叠的处分，我们可以反着画。那么就是重复的部分就是15人。参加数学跟语文兴趣小组的将2个都参加的人重复算了2次，减去一次就可以了。 练习：演练二 例3全班同学共有45人，老师说：“语文作业做完的同学请举手。”结果有30人举手，老师又问：“数学作业做完了同学请举手。”又有20人举手。老师又问：“语文数学一门作业都没完整的请举手。”结果没人举手，有多少同学两门功课都做完？ T：我们来看看将老师提问2次举手的人数加起来，20＋30＝50（人）但是我们全班同学只有45人，为什么会多呢？因为我们把2个作业都做了个同学算了2次。 T：那么我们来看一看多算了几个同学呢？50－45＝5（人）这5个人就是2门都完成了的。
小六数学第9讲：整除和位值原理(教师版)
第九讲整除和位值原理 整除问题 整除是我们很早接触的一个概念，对于它的性质我们也比较熟悉，不过它在题目表现出来的很大的灵活性和很强的技巧性，仍然是值得我们不断学习和思考的．下面我们先回顾一下相关知识： 1.整除的概念 b ，如果a÷b=c，即整数a除以整数b，得到的商是整数c且 a，b，c为整数，且0 没有余数，那么称作n能被b整除，或者是说b能整除a，记作；否则，称为a不能被b整除，或是说b不能整除n．如果整数a能够被整数b整除，则a叫做b的倍数，b叫做a 的约数． 2.整除的基本性质 ①如果a，b都能够被c整除，那么它们的和与差也能够被c整除．即：如果，那么 ②如果b与c的积能整除a，那么b与c都能整除a．即：如果，那么 ③如果c能整除b，b能整除a，那么c能整除a．即：如果 ④如果b，c都能够整除，且b与c互质，那么b与c的乘积能整除a．即： 3.数的整除特征 ①能被2整除的数的特征：个位数字是0，2，4，6，8； ②能被3(或9)整除的数的特征：各位的数字之和能够被3(或9)整除； ③能被4(或25)整除的数的特征：末两位数能够被4(或25)整除； ④能被5整除的数的特征：个位数字是0或5；
⑤能被7(或11、13)整除的数的特征：一个整数的末三位与末三位以前的数字所组成的数之⑥差能够被7(或1、11、13)整除； ⑦能被8(或125)整除的数的特征：末三位数能够被8(或125)整除； ⑧能被11整除的数的特征：奇数位上的数字之和与偶数位上的数字之和的差能够被11整除． 4.位值原理 同一个数字，由于它在所写的数里的位置不同，所表示的数也不同。也就是说，每一个数字除了本身的值以外，还有一个“位置值”。例如“5”，写在个位上，就表示5个一；写在十位上，就表示5个十；写在百位上，就表示5个百；等等。这种把数字和数位结合起来表示数的原则，称为写数的位值原理。 用阿拉伯数字和位值原理，可以表示出一切整数。例如，926表示9个百，2个十，6个一，即926=9×100+2×10+6。根据问题的需要，有时我们也用字母代替阿拉伯数字表示数，如：abc 表示a 个百，b 个十，c 个一。 其中a 可以是1～9中的数码，但不能是0，b 和c 是0～9中的数码。 5.位值原理的表达形式 以三位数为例：100101abc a b c =?+?+? abc 上面的横线表示这是用位值原理表示的一个数，用以区别abc a b c =?? 1.理解整除的概念，会用整除的性质解决有关问题。 2.理解位值原理的含义，能区分位值原理与字母乘法的区别。 3.掌握整除的性质，并熟练应用被2、3、4、5、8、9、11整除的数的特征。 例1：证明：当a c >时，abc cba -必是9的倍数。 分析：abc 与cba 的数字顺序恰好相反，我们称cba 与abc 互为反序数，互为反序数的两个数之差必能被9整除。
5年级-14-容斥原理-难版
第14讲 容斥问题 知识梳理 森林中住着很多动物，据说狮子大王派仙鹤去统计鸟类的种数，蝙蝠跑过去对仙鹤说；“我有翅膀，我应该是属于鸟类的。”于是仙鹤就把蝙蝠统计到鸟类的种类里去了，结果得出森林中一共有80种鸟类。狮子大王又派大象去统计野兽的种类数，蝙蝠听说又来统计兽类了，急忙跑过去对大象说；“我没有羽毛，我应该是属于兽类的。”于是大象就把蝙蝠统计到兽类的种类里去了，结果统计出森林中一共有60种兽类。最后狮子大王问：“森林中共有鸟类和兽类多少种？”狡猾的狐狸听见了仙鹤和大象的统计结果，高兴地向狮子大王汇报：“这还不简单！森林中共有鸟类和兽类140种。”这个统计正确吗？ 同学们肯定会说：“不对！蝙蝠被算了两次，应该再减去一，是139种。”这个故事说明了一个数学问题，那就是被称为“容斥原理”的包含与排除问题。当需要计数的两类事物互相包含（有部分重复交叉）时，应把重复计数的部分排除掉。由此我们得到逐步排除法（容斥原理）：当两个计数部分有重复时，为了不重复计数，应从它们的和中减去重复部分。 容斥原理1 如果被计数的事物有A、B两类，那么，A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数—既是A类又是B类的元素个数。 即A∪B = A+B - A∩B 容斥原理2 如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A 类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A
类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。 即A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C 典型例题 容斥原理1 【例1】★一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？ 【解析】依题意，被计数的事物有语、数得满分两类，“数学得满分”称为“A类元素”，“语文得满分”称为“B类元素”，“语、数都是满分”称为“既是A类又是B类的元素”，“至少有一门得满分的同学”称为“A类和B类元素个数”的总和。 15+12-4=23 【小试牛刀】电视台向100人调查前一天收看电视的情况，有62人看过2频道，34人看过8频道，其中11人两个频道都看过。两个频道都没看过的有多少人？ 【解析】100-(62+34-11)=15 【例2】★一个班有学生48人，每人至少参加跑步、跳高两项比赛中的一项。已知参加跑步的有37人，参加跳高的有40人，请问：这两项比赛都参加的学生有多少人？ 【解析】两项比赛都参加的学生人数，就是参加跑步人数、参加跳高人数重复的部分，排除掉重复部分，所得的就是全体参赛人数，也就是全班学生人数。 40-（48－37）=29人。 【小试牛刀】五年级96名学生都订了报纸，有64人订了少年报，有48人订了小学生报。两种报纸都订的有多少人？ 【解析】用左边的圆表示订少年报的64人，右边的圆表示订小学报的48人，中间重叠部分
集合与容斥原理
第一讲集合与容斥原理 数学是一门非常迷人的学科，久远的历史，勃勃的生机使她发展成为一棵枝叶茂盛的参天大树，人们不禁要问：这根大树到底扎根于何处？为了回答这个问题，在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、生长的。 集合是一种基本数学语言、一种基本数学工具。它不仅是高中数学的第一课，而且是整个数学的基础。对集合的理解和掌握不能仅仅停留在高中数学起始课的水平上，而要随着数学学习的进程而不断深化，自觉使用集合语言(术语与符号)来表示各种数学名词，主动使用集合工具来表示各种数量关系。如用集合表示空间的线面及其关系，表示平面轨迹及其关系、表示方程(组)或不等式(组)的解、表示充要条件，描述排列组合，用集合的性质进行组合计数等。集合的划分反映了集合与子集之间的关系，这既是一类数学问题，也是数学中的解题策略——分类思想的基础，在近几年来的数学竞赛中经常出现，日益受到重视，本讲主要介绍有关的概念、结论以及处理集合、子集与划分问题的方法。 1．集合的概念 集合是一个不定义的概念，集合中的元素有三个特征： （1）确定性设A是一个给定的集合，a是某一具体对象，则a或者是A的元素，或者不是A的元素，两者必居其一，即a∈A与a?A仅有一种情况成立。 （2）互异性一个给定的集合中的元素是指互不相同的对象,即同一个集合中不应出现同一个元素. （3）无序性 2．集合的表示方法 主要有列举法、描述法、区间法、语言叙述法。常用数集如：R , ,应熟记。 N, Z Q 3．实数的子集与数轴上的点集之间的互相转换，有序实数对的集合与平面上的点集可以互相转换。对于方程、不等式的解集，要注意它们的几何意义。 4．子集、真子集及相等集 （1）A?? B A?B或A＝B； （2）A?B?A?B且A≠B； （3）A＝B?A?B且A?B。 5．一个n阶集合（即由个元素组成的集合）有n2个不同的子集，其中有n2－1个非空子集，也有n2－1个真子集。 6．集合的交、并、补运算 x∈} A B={A |且B x∈ x x∈} A B={A |或B x x∈ x?} A∈ {且A =| I x x 要掌握有关集合的几个运算律： （1）交换律A B＝B A，A B＝B A； （2）结合律A （B C）＝（A B） C， A （ B C）＝(A B) C；
小学奥数精讲第四讲 进位制与位值原理
第4讲 进位制与位值原理（二） 同步练习： 1. 计算：102(2014)()= 210(101110)( )= 【答案】见解析 【解析】倒取余数法：102(2014)(11111011110)= 位值原理法：210(101110)(46)= 2. 八进制的1234567化成四进制后，前两位是多少? 【答案】11 【解析】先八进制化为二进制：一位变三位：82(1234567)(1010011100101110111)=；再把二进制化为四进制：两位合一位：24(1010011 100101110111)(1103211313)=.可见，前两位为11. 3. 在几进制中有12512516324?=? 【答案】7 【解析】注意101010(125)(125)(15625)?=，因为1562516324<，所以一定是不到10就已经进位，才能得到16324，所以10