[中學] 一個關於數列的證明

看板Math作者時間5年前 (2020/02/23 18:21), 5年前編輯推噓3(3推 0噓 7→)
留言10則, 3人參與, 5年前最新討論串1/1
遇到了一個關於數列的證明不知道怎麼下手： 必存在一個由0、1組成且總和為k的n項數列，其中的連續任m項總和均 >= p 當k/n >= p/m時。 簡單說我想要證明　 由0,1組成的原數列一定有一個排列， 能夠讓我任擷取一段，都滿足一個給定的比較小的比例。 想求教版上的大家 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.242.10.21 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1582453268.A.A33.html ※ 編輯: farewell324 (111.242.10.21 臺灣), 02/23/2020 18:32:52
推
02/24 02:43, 5年前 , 1F
直接構造然後小心估計吧？盡量均勻地放1。如果n是
02/24 02:43, 1F
→
02/24 02:43, 5年前 , 2F
3k，就重複0,1,0這樣。0,0,1和1,0,0應該也可以。
02/24 02:43, 2F
推
02/24 02:57, 5年前 , 3F
前m-p項為0, 接著連續p項為1, 重複這樣直到總共n項
02/24 02:57, 3F
→
02/24 02:57, 5年前 , 4F
此時總和會<=k 最後任意將一些0改成1使總和為k即可
02/24 02:57, 4F
→
02/24 02:57, 5年前 , 5F
例如(k,n,p,m)=(5,8,3,5)會先構造出00111001, 再把
02/24 02:57, 5F
→
02/24 02:57, 5年前 , 6F
其中一個0換成1就完成了
02/24 02:57, 6F
→
02/24 03:05, 5年前 , 7F
不先放1是因為怕總和超過k 如先前例子會變11100111
02/24 03:05, 7F
推
02/26 02:56, 5年前 , 8F
直接看最差的狀況 ，所有的零都排在一起，然後你剛
02/26 02:56, 8F
→
02/26 02:56, 5年前 , 9F
好取到最多的零。如果這樣都可以那就可以了。
02/26 02:56, 9F
→
02/26 02:57, 5年前 , 10F
啊不好意思題目看錯了欸嘿
02/26 02:57, 10F
‣ 更多 farewell324 的文章
文章代碼(AID): #1UKb8Kep (Math)