[其他] 一題有趣的數學題

看板Math作者utomaya (烏托馬雅)時間2年前 (2023/09/21 22:47)推噓4(4推 0噓 8→)

留言12則, 3人參與討論串1/1

通常我不會來這推薦ProjectEuler的題目不過這題實在太有趣，我覺得可以介紹給大家如同很多題目一樣，厲害的不是解出來的人，而且出題者別具匠心的巧思可以想出這種題目。題目的連結: https://projecteuler.net/problem=855 英文出題以下是翻譯：(不是逐字翻，大概翻一下就好，如果覺得我翻得不好可以看原文) Alex跟Bianca在玩一個遊戲，這個遊戲先給2個正整數a,b，則遊戲的回合數為a*b回合。遊戲開始時有一個邊長為1的正方形紙張，每一回合Alex將紙張水平切了a-1刀，垂直切了b-1刀，將紙張分割成a*b個小矩形，切割的線不必均勻分布，任兩刀可以重合，也可以和紙張的邊緣重合(注：也就是說可以有矩形面積為0)，這些小矩形從上到下，由左至右編號為1,2,3,...,a*b。接下來Bianca從這些小矩形中選一個出來作為下一回合使用，但是Bianca不可以選之前回合已經選過的號碼。 Bianca想要最小化最後紙張的面積，而Alex想要最大化該面積。令S(a,b)為最後紙張的面積，假定兩人都用最佳策略在進行該遊戲。例如，S(2,2)=1/36，S(2,3)=1/1800 ≒ 5.5555555556e-4 試求S(5,8)，將你的答案以科學記號進位到小數點後10位數，以小寫英文字母e分隔首數與尾數。 --------------------------------分隔線------------------------------ 以下是解題的心路歷程，但不會有解答，因為PE的主辦方不太希望我們在外透露解法：如同大部份的PE題目一樣，一開始狀態非常混沌，完全不知道從哪下手？只知道好像是這樣，每一回合Bianca選個一個號碼以後，下一次Alex的分割的方法就會不一樣。不同的號碼，就會有不同的分割法。以S(2,2)來說，如果每一回合Alex都將紙張分割成4個同樣大小的正方形，那麼最後紙張的大小會是(1/4)^4 = 1/256，而不是題目提示的最大值1/36。順手紙筆算了一下，好像可以得到S(2,2) = 1/36，但是離S(5,8)還有一大段距離。只好等待A-ha時刻的來到，不是唱Take on me的那個A-ha樂團而是當你忽然想到關鍵的解法時，會驚呼一聲「A-ha，原來是這樣！」的那個A-ha時刻。 https://www.youtube.com/watch?v=xqTBlft8gQA

然後就沉沉睡去，還好這次我的A-ha moment沒有太晚來到，在睡夢中忽然想到會不會是指那個？趕快起床用紙筆算了一下，玩了幾盤，果然是那個！沒有太多時間證明，趕快把程式寫一寫，把答案上傳上去。完全正確，第37位！後來在傳完答案後的幾小時內，我給出了證明，並完全瞭解為何這樣是最大值？通常ProjectEuler需要跑程式，但這題只需要按計算機，當然是指Windows上那種工程計算機，這算是一個提示吧！對了，再次提醒，PE主辦方不太希望有玩家在外透露答案，請勿在此寫出答案。如果你有自信你的答案是對的，請在ProjectEuler註冊帳號 https://projecteuler.net/ 登入後輸入答案，你的帳號將出現在fastest table上，把自己的id印在fastest table上是很酷的一件事。但只有前100位正解者會列在fastest table上，超過100位解出來者，就榜上無名了，這題目前只有61位解出來。以上 -- 王菲成英姝吳明益張雨生崔健陳珊妮南西‧威爾森(Nancy Wilson) 紅心合唱團譚維維希莉娜依高圓圓 Deborah Harry 金髮美女合唱團(Blondie) 楊乃文中森明菜小紅莓(The Cranberries) 數學 ProjectEuler 解題網站 80年代西洋音樂小泉今日子 In the fall we sleep all day https://projecteuler.net/recent 歐拉編程競賽 https://projecteuler.net/problem=855 最新一題是個困難題 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.115.129.34 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1695307660.A.5A9.html ※ 編輯: utomaya (58.115.129.34 臺灣), 09/22/2023 00:34:26

推

LPH66

09/22 07:23, 2年前 , 1^F

09/22 07:23, 1^F

推

LPH66

09/22 09:05, 2年前 , 2^F

09/22 09:05, 2^F

→

LPH66

09/22 09:06, 2年前 , 3^F

09/22 09:06, 3^F