[理工] [離散] 鴿籠原理

看板Grad-ProbAsk作者 (沒錢了...衰)時間15年前 (2010/07/25 22:05), 編輯推噓9(9推 0噓 11→)
留言20則, 6人參與, 最新討論串2/9 (看更多)
1. Given A1,...,An 屬於Z(整數),證明:存在i≦j 使得n|(Ai+...+Aj) pf: 令 X1=A1,X2=A1+A2,.....Xn=A1+A2+...+An ∴存在p ﹤q 使得 n|(Xq-Xp) (小弟就是卡在這裡，不懂為什麼這個成立) =>n|(Ap+1+...+Aq) (那個p+1是第p+1項的意思，不會用下標= =) 這是我朋友的筆記 證明只寫到這裡 因為他也看不懂 所以就PO上來問= =... 2. 9台電腦連到5台印表機，需要幾條線保證任5台電腦皆可連到5台不同的印表機? Ans: 5+4*5=25 (完全不知道他的想法...) 這兩題我都看不出來跟鴿籠原理有什麼關係 囧 麻煩各位高手指導一下 感恩... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.163.161.39
推
07/25 22:31, , 1F
第一題題目是不是不完整阿? A1~An是不是"連續"整數?
07/25 22:31, 1F
→
07/25 22:33, , 2F
或是A之間的大小關係? 不然怎麼一直強調i j p g的大小?
07/25 22:33, 2F
→
07/25 22:48, , 3F
沒有耶 題目就這樣而已= =
07/25 22:48, 3F
推
07/25 22:58, , 4F
2.先挑5台電腦 各連1台印表機 剩下的4台電腦每台印表機]
07/25 22:58, 4F
→
07/25 22:59, , 5F
都連 5+4*5=25 .... 我承認我在湊答案 XDD
07/25 22:59, 5F
→
07/25 23:01, , 6F
我也是跟y大想法一樣 不過我得承認是看到答案才會這樣想.
07/25 23:01, 6F
→
07/25 23:02, , 7F
沒看到答案根本想不出來 而且這跟鴿籠有什麼關係 囧
07/25 23:02, 7F
推
07/25 23:03, , 8F
這樣想應該沒錯吧 任拔掉一條線 題目的要求就不滿足了
07/25 23:03, 8F
推
07/25 23:18, , 9F
第一題感覺少了一個An+1 這樣n+1個數對應到0~n-1個餘數
07/25 23:18, 9F
→
07/25 23:20, , 10F
使得必有兩數同餘 設Ai同餘Aj mod n 不失一般性假設i<j
07/25 23:20, 10F
→
07/25 23:20, , 11F
故 n|Aj-Ai 不知是不是少了一個An+1
07/25 23:20, 11F
推
07/25 23:22, , 12F
我有疑問 如果不是"連續"整數的話餘數也不一定會填滿吧
07/25 23:22, 12F
推
07/25 23:33, , 13F
若是有n+1個數 不管有沒有連續 他mod n 的餘數都會落在
07/25 23:33, 13F
→
07/25 23:33, , 14F
0~n-1之間 (n個數) n+1個數要對應到n個餘數 再用鴿籠原理
07/25 23:33, 14F
→
07/25 23:34, , 15F
相關證明在小黃上冊2-84頁例題58有
07/25 23:34, 15F
推
07/25 23:43, , 16F
n=3 然後(n+1)個數3,6,9,12 ?
07/25 23:43, 16F
推
07/25 23:48, , 17F
我懂了我真蠢 不一定填滿 但是一定有重複
07/25 23:48, 17F
→
07/25 23:50, , 18F
題目沒錯，應該是筆記少寫 "X0=0" 這行
07/25 23:50, 18F
推
07/25 23:55, , 19F
對耶 整除就不需要同餘互減了 大家都好強XD
07/25 23:55, 19F
→
10/24 12:06, , 20F
故 n|Aj-Ai 不 https://daxiv.com
10/24 12:06, 20F
‣ 更多 vn801368 的文章
文章代碼(AID): #1CJ4IQXM (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 2 之 9 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共9篇)
‣ 更多 vn801368 的文章
文章代碼(AID): #1CJ4IQXM (Grad-ProbAsk)