我又有一個演算法的問題百思不得其解，不知道有沒有人有什麼想法呢？ 問題: 假設有一個社區要挖井。為了讓每一口井平均分配，有以下的規則： 第一口井要在(0, 1)之間。(這是open interval)。 第二口井中的第一口要在(0, 1/2)之間，第二口要在(1/2, 1)之間。 第三口井中的第一口要在(0, 1/3)之間，第二口要在(1/3, 2/3)之間， 第三口要在(2/3, 1)之間。 第i口井的話，這些井要在(0, 1/i), (1/i, 2/i), ... ((i-1)/i, 1) 之間。 每一次挖井時舊的井的位置是不能改變的。 根據這樣的規則，可以挖無限多口井嗎？如果不能，最多可以挖幾口井？ 目前的想法： 假設可以挖無限多口，用歸納法，先證2^n口都可以挖的出來，然後推 2^n到2^(n-1)也都可以得到（也就是從2^n口開始一個井一個井拿掉直 到2^(n-1)口為止，且這2^(n-1)口井的位置要和之前證的一樣）。 要證2^n口井很容易，例如可以放在(1/n)-d的地方，d < 1/2^n。但是從 2^n如何到2^(n-1)就不知道如何證了。而且這樣的放法也是不對的， 我試過16口井想要推到8口，15, 14口井都可以成功，但推到13口時 就會出問題。所以我想不知道這樣做對不對，還是有別的方法呢？ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.75.133.138