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