組合數學基礎-問題與練習.

1、組合數學基礎 - 問題與練習（陶平生）基本內容與方法：組合計數；組合構造；組合結構；映射與對應；分類與染色；歸納與遞推；容斥原理；極端原理；調整法；補集法；數形結合法，等等1、 設M為 n 元 集 ， 若M有 k個不同的子集A1, A2 , Ak，滿足：對于每個i , j1,2, k， AiA j，求正整數k的最大值2 、將前九個正整數 1,2, ,9 分成三組， 每組三個數， 使得每組中的三數之和皆為質數；求出所有不同分法的種數3 、設正整數 a 的各位數字全由 1和 2組成，由其中任意kk 2 個連續(xù)數位上的數字所組成的 k 位數，稱為數 a 的一個“ k 段”；若數 a 的任兩個“k 段

2、”都不相同證明：對于具有這種性質的最大正整數a ，其開初的一個 “ k1段”和最后的一個 “ k 1段”必定相同 .4 、將數集 A a1, a2 ,., an 中所有元素的算術平均值記為P(A) ，（ P(A)a1 a2. an ） . 若 B 是 A 的非空子集，且P(B) P( A) ，則稱 B 是 An的一個“均衡子集” 試求數集 M 1,2,3,4,5,6,7,8,9 的所有“均衡子集”的個數5 、某校有 2010 名新生，每人至少認識其中 n 人，試求 n 的最小值，使得其中必存在彼此認識的 16 個人 .6 、有 nn2 名運動員，其編號分別是1,2, n ，在一次活動中，他們以

3、任意方式站成了一排 .如果每次允許將其中一些人兩兩對換位置，但在同一輪操作過程中, 任一人至多只能參與一次這種對換.證明：至多只需兩輪這樣的操作，可使隊列變成1,2, n的順序排列 .7 、稱自然數 a 開初若干位數字組成的數為 a 的“前綴” . 例如， 2,20,201,2011 都是數 2011 的“前綴” .證明：對于任一給定的正整數M ，存在正整數n ，使 M 為 2n 的“前綴” .8 、對于 2n 元集合 M1,2,2 n ，若 n 元集 Aa1 , a2 , an，B b1, b2 ,bn 滿足： A Bnn，則稱 AB是集 MM,A B，且akbkk1k 1的一個“等和劃分”

4、 （ AB 與 BA 算是同一個劃分） 試確定集 M1,2,12 共有多少個“等和劃分” 9、對于由前2n 個正整數構成的集合M1,2,2 n ，若能將其元素適當劃分，排成兩個 n 項的數列： A(a1, a2 , an ), B (b1, b2 , , bn ) ，使得 akbkk , k 1,2, n ，則稱 M 為一個友誼集，而數列A, B 稱為 M 的一種友誼排列，例如A(3,10,7,9,6)和B (2,8,4,5,1) 便是集合 M1,2, ,10 的一種友誼排列，或記為3,10,7,9,6；2, 8, 4, 5,1(10 ) 、證明：若 M1,2,2 n 為一個友誼集，則存在偶數

5、種友誼排列；(20) 、確定集合 M11,2,8 及 M 2 1,2, ,10 的全體友誼排列10 、一副紙牌共52 張，其中“方塊” 、“梅花”、“紅心”、“黑桃”每種花色的牌各13 張，標號依次是2,3,10, J ,Q , K , A ，其中相同花色、相鄰標號的兩張牌稱為“同花順牌”，并且A 與 2 也算是順牌（即A 可以當成1使用） .試確定，從這副牌中取出13 張牌，使每種標號的牌都出現(xiàn)，并且不含“同花順牌”的取牌方法數11、一副三色牌，共有紙牌32 張，其中紅黃藍每種顏色的牌各10 張，編號分別是1,2,10；另有大小王牌各一張，編號均為0 ，從這副牌中任取若干張牌，然后按如下規(guī)則

6、計算分值： 每張編號為 k 的牌計為“好”牌組試求 “好”牌組的個數2k分，若它們的分值之和為2004 ，就稱這些牌為一個12 、奧運會排球預選賽有n 支球隊參加，其中每兩隊比賽一場，每場比賽必決出勝負，如果其中有 k （ 3 kn ）支球隊 A , A , A，滿足： A勝 A， A勝 A3， ， A12k122k 1勝 Ak ，Ak 勝A1 ，則稱這k 支球隊組成一個k階連環(huán)套；證明：若全部n 支球隊組成一個n 階連環(huán)套，則對于每個k（3kn ）及每支球隊Ai1in， Ai 必另外某些球隊組成一個k 階連環(huán)套.13 、任意給定nn2個互不相等的n 位正整數，證明：存在k1,2, n，使得將

7、它們的第k 位數字都刪去后，所得到的n 個 n1位數仍互不相等.14 、桌面上放有2011 枚硬幣，其中有的正面朝上，其余的正面朝下，今有次按如下方法翻轉硬幣：第一人翻轉其中的一枚，第二人翻轉其中的兩枚， ，第其中的 k 枚， ，第 2011 人則將 2011 枚硬幣全部翻轉2011 人依k 人翻轉證明：1、不論硬幣最初正反面的分布情況如何，他們總可采取適當的步驟，使得2009人都操作之后，恰使所有的硬幣朝同一個方向；2 、硬幣最后的統(tǒng)一朝向，只依賴于初始分布，而與具體的翻幣方案無關15 、平面上任給 16 個點，每兩點間的距離不超過1；證明：其中必有兩點，它們間的距離不超過12 416 、某

8、選區(qū)有 1000 個選民，分別持有編號為000,001,002, ,999 的選票，選區(qū)共設有100 個投票站，編號分別是 00,01,02, ,99 選區(qū)制定了一條法律：規(guī)定選民z 如果要將選票投到票站A ，只有當該選民所持有的選票號碼中，若去掉其中某一數碼后，剩下的兩位數恰好就是該票站的號碼時方可進行，（例如，持 135 號票的選民，只能到13,15,35 號票站之一去投票） ；問，在這一法規(guī)下，該選區(qū)最多可以關閉多少個投票站，使得剩下的投票站還能確保選舉照常進行？17 、在平面直角坐標系中給定100 邊形 P ，滿足： 10、 P 的頂點坐標都是整數；20、 P 的邊都與坐標軸平行；30

9、、 P 的邊長都是奇數證明： P 的面積為奇數18 、 mn 矩形 ABCD 的一組鄰邊之長為：ABm, ADn ，其中 m,n 是互質的正奇數，該矩形被分割成mn 個單位正方形， 設矩形的對角線AC 與這些單位正方形的邊相交，順次得到交點A1 , A2 , Ak （其中 A1A, AkC ）k 1試求( 1) j 1 A j A j 1 的值j 119 、邊長為 n 的菱形 ABCD , 其頂角 A 為 60o , 今用分別與AB, AD 及 BD 平行的三組等距平行線 ，將菱形劃分成2n 2 個邊長為 1 的正三角形( 如圖所示 ). 試求以圖中的線段為邊的梯形個數s n .20 、某學校有2011名學生，學號分別是1,2,2011 ，該校的會場恰有2011 個座位，分別編號為1,2,2011 ，學生的每次集會都是不用對號入座的；如果在一次集會中，任一個學號為k 的學生都不坐在k 號位，且任意n 個學號為ak1, ak2, akn的學生，其座位號集合 k