※ 引述《mikek (rabbit)》之銘言：
: ※ 引述《changkh (留學生涯)》之銘言：
: : 沒錯，就是這樣子。
: : 所以覺得蠻難想的。
: Sorry, I can't type Chinese right now.
: I hope the solution below is correct. It's just for your information.
: Assume there are n wells.
: The position d(k) of the k-th well has to satisfy all of the following
: conditions:
: (k-1)/k < d(k) < k/k which is the valid interval if there are k wells
: (k-1)/(k+1) < d(k) < k/(k+1) which is the valid interval if k+1 wells
: ...
: (k-1)/n < d(k) < k/n which is the valid interval if there are n wells
: Note that for all wells (i.e. k=1,2,3,...,n), the above inequalities must
: hold.
這樣看起來好像是有假設第k個都在k/i的地方，對於i>=k。可是其實是不一定的。
例如原來在2/5區間內的可能之後會變成到4/10區間的井。
: So we only need to check k=1 (n<inf) and k=2 (n<4).
: Therefore, the number of wells is at most 3 (n<4).
目前我試過的井數最多是成功到八個井。之後有些複雜，所以還沒試過。所以我想
不只三個井。不過還是謝謝你啦。因為你的式子，我有了新的想法，但是還是不完全。
假設在第k步，加了井在di，而它在(j-1)/k<di<j/k區間。
若此井造成未來某區間已有兩個井，設是它和它目前左邊那個井造成的，若該
井是dl, 則它在(j-2)/k<dl<(j-1)/k之間。
假設dl和di在m個井時已在同一區間，設是在(p-1)/m到p/m的區間之中。
則可以得到
(j-1)/k<di<p/m
(p-1)/m<dl<(j-1)/k
兩式相加、即減得到di+dl, di-dl，可以再解出一個di和dl的範圍:
1/2((p-1)/m+(j-1)/k) < di < 1/2(2p/m+(j-1)/k)
1/2((j-1)/k-1/m) < dl < 1/2(p/m+(j-1)/k)
如果在這個範圍內，那di和dl會滿足 k個井時的條件，但是在m個井時已經在
同一區間內。
但是接下來要怎麼做就不知道了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.43.196.35