Re: [中學] 建中數學通訊解題120期4號題(數論類型)

[freePrester (Prester)]

※ 引述《thr3ee (亞澤蛙 妮可)》之銘言：
: 建中通訊網址: goo.gl/NrI3po(請選擇120期下載, 該卷第12004題)
: 我沒參加過這個活動, 昨天剛好點到下載, 就看了下題目
: 其中有道題不好解, 題目如下:
: 2015個都不等於119的正整數a_1,...,a_2015排成一數列,
: 其中任意連續若干項之和都不等於119, 求這2015個數總和的最小值為?
: 我猜, 最小值應該發生於a_1=...=a_2015=2的時候,
: 如果只由1與2組成的數列, 會跑出一堆總和119;
: 如果由1與3以上的數來取代2, 1太少總和會比全2大, 1太多又會跑出119;
: 不過找不到轉換"非和119"條件的方法, 所以沒動手做
: 請教各位有什麼好方法來解這題?
: --------------------------------------------------------
: PS: 因為我對這題難度有點疑惑, 就去翻了翻其他的題目
: 看起來幾乎都是高中輔教上的熟客, 沒道理偷藏一題這種複雜題才對
: 說不定這題能夠用高中工具三兩行就解出來?

           n
設 S(n) = Σ  ak ，則題目可改寫為求當 i > j 時 S(i) - S(j) ≠ 119
          k=1

所求為 S(2015) 的最小值

因 S(n) 遞增，所以 S(k+1) - S(k) ≧ 1 ，又要使所求最小

可知在 n = 1~119 時

        S(1) = 1 、 S(2) = 2 、 ... 、 S(119) = 119

在 n = 120 時，因 S(120) 減去前面連續 119 個數都不可為 119 ，

        所以 S(120) 最小只能為 S(119) + 119 + 1 = 239

        且當 n = 121~238 時 S(n) 分別為 240 、 241 、 ... 、 357

在 n = 239 時，同理 S(n) 不能和前面連續 119 個數之差為 119 ，

        所以 S(239) 最小為 S(238) + 119 + 1 = 477 ...

以此類推，可知當 n = 119*k + r 時， S(n) 的最小值為 119 * 2k + r

又 2015 = 16 * 119 + 111 => S(2015) 最小值為 2 * 16 * 119 + 111 = 3919

最小數列為 1,1,1,...,1,120,1,1,1,...,1,120,1,1,...

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.188.152
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1441898472.A.295.html
※ 編輯: freePrester (114.37.188.152), 09/10/2015 23:22:02
→ thr3ee      : 這樣只是找出一種可能的答案, 並沒有證明出"最小"
→ thr3ee      : 感覺起來1夠多就很小, 但說不定拿掉120反而更小
→ freePrester : 你要"整數"又遞增，每項只能多1啊
→ freePrester : (針對S而言)
→ thr3ee      : 換言之, 也許S(1)~S(119)都非最小時, S(120)才最小
→ thr3ee      : 簡述你的做法: 因S(120)最小, 故S(1)~S(119)最小
→ thr3ee      : 故a_1=...=a_119=1, 有些矛盾吧, 關鍵沒證明出來
→ freePrester : 我打完才看到L大有寫類似的東西…
→ freePrester : 我有想過用同餘、類似鴿籠的方法去證
→ freePrester : 但中間又卡了一些東西…
→ freePrester : 這部份再請高手補完
→ thr3ee      : 有的, 解法在原篇推文有人貼了, 我只是多嘴而已
→ freePrester : 我有看過文章…我不覺得那個證明完整= =
→ freePrester : 我再想想看好了
推 LPH66       : 其實就是因為這一點難證我的推文才說那是直覺來的
→ LPH66       : 不過我倒是有想到一個可能證明的理由:
→ LPH66       : 因為和數列任兩數不得差 119, 每連續 238 個自然數
→ LPH66       : 在和數列裡只會有至多 119 個
→ LPH66       : 由此"猜"出和數列連續 119 項要 cover 238 自然數
→ LPH66       : 那連結裡的證明是原數列任何連續 119 個數之和
→ LPH66       : 至少是 238, 從這一點來看這應該是這題的核心
→ LPH66       : 我的"直覺理由"其實就是用和數列"猜"出這個事實
→ doom8199    : 這篇應該不算證明吧, 只是單純的 greedy alg.
→ doom8199    : 把 (1,120,1) 換成 (2,118,2),or   2,(2,116,2),2
→ doom8199    : 也都能 fit 你宣稱的 min, 但 rule 卻不一樣
→ doom8199    : 當然換這前提要把序列做 shift