gauss_legend77 10 發表於 May 20, 2010 檢舉 Share 發表於 May 20, 2010 1.4個a、2個b、2個c、2個d進行排列,相同字母不得相鄰的排法有幾種?2.10個人任意排成一列,證明:必有四個人按照高矮順序。3.假設一個議題有甲,乙,丙三個方案,10個人採無記名表決,或許會有廢票,問開票解果中,甲的得票數超過總票數的一半情況有幾種?4.設A,B,C,D,E屬於{1,2,3,4,5},則使(A-B(B-C)(C-D)(D-E)(E-A)=0的方法有幾種小弟不材,請各位大大高抬貴手替在下解答:'(:'(:'(:'(:'(:'( 鏈接文章 分享到其他網站
Auron 10 發表於 May 20, 2010 檢舉 Share 發表於 May 20, 2010 (已編輯) 1.4個a、2個b、2個c、2個d進行排列,相同字母不得相鄰的排法有幾種?這好像要討論很多種情形Re #3 曾阿牛 我是想說要先討論a相鄰的情形,因為(aa,aa)和(aaa,a)是不一樣的情況,然後再用任意排-相鄰的情形,這樣就能求同字母不相鄰的排法。這樣應該沒錯吧2.10個人任意排成一列,證明:必有四個人按照高矮順序。等高手3.假設一個議題有甲,乙,丙三個方案,10個人採無記名表決,或許會有廢票,問開票結果中,甲的得票數超過總票數的一半情況有幾種?總票數是10票嗎???廢票的要算嗎???如果是10張的話就甲得六張、七張、八張、九張、十張,剩餘的就另外兩個分配廢票的不算進總票數的話就比較麻煩,不過還是差不多4.設A,B,C,D,E屬於{1,2,3,4,5},則使(A-B)(B-C)(C-D)(D-E)(E-A)=0的方法有幾種任意選-五個全都不相等的有錯請跟我說一聲 此內容已被編輯, May 21, 2010 ,由 Auron 鏈接文章 分享到其他網站
曾阿牛 10 發表於 May 20, 2010 檢舉 Share 發表於 May 20, 2010 Re #2 Auron 關於第一題 題目說:相同字母不得相鄰 所以我看不懂你的做法Re #1 gauss_legend77 雖然看得懂第二題在問什麼 不過我還是要抱怨一下題目敘述的太簡短 鏈接文章 分享到其他網站
I'm‧泥〃 11 發表於 May 21, 2010 檢舉 Share 發表於 May 21, 2010 (已編輯) 我是想說要先討論a相鄰的情形,因為(aa,aa)和(aaa,a)是不一樣的情況,然後再用任意排-相鄰的情形,這樣就能求同字母不相鄰的排法。這樣應該沒錯吧相鄰有 ( aa相鄰 且 另外兩個aa不相鄰 )、( aa相鄰 且 另外兩個aa相鄰 )、( aaa相鄰 )、( aaaa相鄰 )、( bb相鄰 )、( cc相鄰 )、( dd相鄰 )前三項不可能同時成立所以不用考慮同時出現其他的話還要扣掉 xx相鄰 且 yy相鄰 的可能 ...整個算起來其實是相當複雜 = =' 此內容已被編輯, May 21, 2010 ,由 I'm‧泥〃 鏈接文章 分享到其他網站
black40114 10 發表於 May 21, 2010 檢舉 Share 發表於 May 21, 2010 學弟你瘋了 - -第一題 好複雜= = 只會第三題 因該是H 4 4 = 35種 是麻 = =? 鏈接文章 分享到其他網站
gauss_legend77 10 發表於 May 22, 2010 作者 檢舉 Share 發表於 May 22, 2010 第二題就是說10個高矮不同的人,排成一列,必會有4個人(不一定要相鄰)照高矮順序排。例如9、1、8、2、7、3、6、4、5、10第一題可以解釋地清楚一點嘛@@小弟才疏學淺 鏈接文章 分享到其他網站
曾阿牛 10 發表於 May 22, 2010 檢舉 Share 發表於 May 22, 2010 (已編輯) Re #6 gauss_legend77 謝謝您對第二題的的解釋 關於第三題 #2 Auron 大大所問的也是我想問的 您還沒提出說明至於第一題 這麼多大大都還沒提出答案的數據 我猜主要的原因是算不下去如果用排容原理的話 計算上會遇到重重困難題目如果只有兩個 a 的話 用排容原理就好辦事 只可惜不是看樣子 四個 a 把事情搞砸了 不過那是對排容原理而言這四個 a 卻讓"各個擊破法"變得還算有效率10個字母裡既然有4個 a 那我用 a 在排列裡的位置 來將問題分類第一型: _a_a_a_a ( 也包括 a_a_a_a_ ) 第二型: _a_a_a_a_ 第三型: a_a_a_a底線表示至少要放 a 以外的一個字母 並滿足相同字母不相鄰的要求結果 第一型有 1152 第二型有 360 第三型有 374 共 1886樓主若有答案的話 幫我對一下吧 謝謝 此內容已被編輯, May 22, 2010 ,由 曾阿牛 鏈接文章 分享到其他網站
actino 10 發表於 June 3, 2010 檢舉 Share 發表於 June 3, 2010 第一題排容應該還是可以做AAABBCDE--->960 這是有正確答案 有興趣的可以試一下自己的方法想法是"訂報紙" 目標A不相鄰∩B不相鄰∩C不相鄰∩D不相鄰在A不相鄰的情況下A不相鄰B不相鄰∩A不相鄰C不相鄰∩A不相鄰D不相鄰 (由四個交集變成三個)=A不相鄰全部可能 - A不相鄰B相鄰 - A不相鄰C相鄰 - A不相鄰D相鄰 + A不相鄰B相鄰C相鄰 + A不相鄰B相鄰D相鄰 + A不相鄰C相鄰D相鄰 - A不相鄰B相鄰C相鄰D相鄰第一項先排bcd 6!/2!/2!/2!* (C7取4 安插a不連)第二、三、四項先排bcd 5!/2!/2!* (C6取4 安插a不連) (b連 就把b圈起來兩個當成一個)同理可做c連 d連第五、六、七項先排bcd 4!/2!* (C5取4 安插a不連)一樣三項相同最後一項先排bcd 3!* (C4取4 安插a不連)這樣算出來是3024感覺跟樓上差有點多,是不是我算錯了~~~ 鏈接文章 分享到其他網站
曾阿牛 10 發表於 June 4, 2010 檢舉 Share 發表於 June 4, 2010 大大的確算錯了 但做法是正確的 而且比我的做法簡單太多了用大大的做法 我算出來是 1976 比我的答案多 90於是 重新用我的做法再算一次 發現當時忽略了第一型之中的一種情況 所以算出來比較少感謝大大的分享 讓我獲益良多 鏈接文章 分享到其他網站
howt 10 發表於 June 7, 2010 檢舉 Share 發表於 June 7, 2010 大大的確算錯了 但做法是正確的 而且比我的做法簡單太多了用大大的做法 我算出來是 1976 比我的答案多 90於是 重新用我的做法再算一次 發現當時忽略了第一型之中的一種情況 所以算出來比較少感謝大大的分享 讓我獲益良多我用遞迴算是1974,事實上答案應該要是6的倍數,因為bcd的個數是對稱的,而其排列置換有6種。第二題可以用點線圖證明,方法是先證明五個點必有3點遞增或遞減,然後令原題目中的56點連線是正的,由題目的要求可知道15、25、35、45全為負或67、68、69、610全負,如此分析下去即可證明,不過我認為這不是一個好方法。第三題題意不清,但答案跟前幾樓說的一樣,並不難。第四題用遞迴可解出答案為 4^5 + 4*(-1)^5 = 1020,一般化後的答案是(m-1)^n + (m-1)*(-1)^n ,n是排列數,m是集合內有幾個相異元素。 鏈接文章 分享到其他網站
曾阿牛 10 發表於 June 8, 2010 檢舉 Share 發表於 June 8, 2010 :| 呃...... 我在 #9 打錯了 應該是 1974 與大大的答案相同敢問大大的遞迴關係是如何建立的? 鏈接文章 分享到其他網站
howt 10 發表於 June 9, 2010 檢舉 Share 發表於 June 9, 2010 (已編輯) 定義F(w,x,y,z)表示題目要求的方法數(顯然w、x、y、z本身的排列不影響F的值)原題要求F(4,2,2,2),考慮F(5,2,2,2)與F(4,2,2,2)的關係:在F(4,2,2,2)中插入一 個a使其對應到F(5,2,2,2),總共有11個空格,但有8個不能選(與a相鄰),因此每個F(4,2,2,2)中的排列可以對應到3個F(5,2,2,2)的排列。再考慮從F(5,2,2,2)中拿掉一個a,有5種拿法,但必須注意的是若排列中有形如xax這種排列,則拿掉後不會對應到F(4,2,2,2),而F(5,2,2,2)中具有bab的排列數為F(4,1,2,2)(可以想成bab變成一個新的b)於是有5F(5,2,2,2) - 3F(4,1,2,2) = 3F(4,2,2,2) (就像連連看一樣,一邊的總線數等於另一邊)依此想法可得到:(為了省去打字麻煩,令F(n,2,2,2)=J(n)、F(n,2,2,1)=K(n)、F(n,2,1,1)=L(n)、F(n,1,1,1)=M(n) )nJ(n) = (8-n)J(n-1)+ 3K(n-1)nK(n) = (7-n)K(n-1)+ 2L(n-1)nL(n) = (6-n)L(n-1)+ M(n-1)nM(n) = (5-n)M(n-1)值得一提的是n越大F越好算,顯然我們有F(x+y+z+1,x,y,z) = (x+y+z)!/(x!y!z!)此外 nX(n) = (a-n)X(n-1)的通解為X(a-1)*C(a-1,n),C是組合數由以上可得M(n) = 6C(4,n)n[M(n)+L(n)] = (6-n)[M(n-1)+L(n-1)] => L(n) = 12C(5,n) - 6C(4,n)n[M(n)+2L(n)+K(n)] = (7-n)[M(n-1)+2L(n-1)+K(n-1)]=> K(n) = 30C(6,n)-24C(5,n)+6C(4,n)n[M(n)+3L(n)+3K(n)+J(n)] = (8-n)[M(n-1)+3L(n-1)+3K(n-1)+J(n-1)]=> J(n) = 90C(7,n)-90C(6,n)+36C(5,n)-6C(4,n) = 90C(6,n-1)+36C(5,n)-6C(4,n)J(4) = 90*20 + 36*5 - 6 = 1974上面是一般化的結果,如果直接算其實也不用搞這麼多,不過這個遞迴關係可以用來推廣到更高階的部分(譬如說就算b不只兩個,那bab的作用還是等價於一個b)。 此內容已被編輯, June 9, 2010 ,由 howt 鏈接文章 分享到其他網站
曾阿牛 10 發表於 June 12, 2010 檢舉 Share 發表於 June 12, 2010 Re #12 howt 嗯嗯了解大大的想法了 雖然細節沒有仔細看感謝 howt 大大的分享 鏈接文章 分享到其他網站
howt 10 發表於 September 29, 2010 檢舉 Share 發表於 September 29, 2010 2.10個人任意排成一列,證明:必有四個人按照高矮順序。利用反證法。不妨令十人身高為An且不相等,現在將其任意排成一列:A1、A2....A10定義Bj為從Aj開始算起的最大遞增數(包含自己)ex: 10 9 8 7 6 5 4 1 2 3,其中A8=1,B8=3假設不存在Bj>3,那麼所有的Bn必定只能在(1,2,3)中選取,由鴿籠原理知存在四數w<x<y<z,使得Bw=Bx=By=Bz,且Aw>Ax>Ay>Az (若Aw<Ax則表示Bw>Bx,矛盾),但Aw>Ax>Ay>Az 即表示存在由四數構成的遞減序列。也就是任意十個數排列必有四數遞增或遞減。 鏈接文章 分享到其他網站
Recommended Posts
請登入後來留意見
在登入之後,您才能留意見
立即登入