[代數] 找兩個離散函數的顯式

[znmkhxrw (QQ)]

 
請教一下這個問題:
 
令N為自然數
令S:= N+(N-1)+...+1 = (N+1)*N/2
令i€{1,2,...,S}
 
我們把S拆成N, N-1, N-2,...,1共N組, 第一組有N個1加起來, 第N組有1個1加起來
即第k組有(N-k+1)個1加起來
因此對於任何i, 我們都能定義一組唯一的數對i=(a_i, b_i)
其中a_i是所在的第幾組, b_i是這一組的第幾個(照i遞增排列)
 
如下N=4的舉例:
S = 10
i€{1,2,...,10}
 
N=4:   i=1 → (a_i,b_i) = (1,1)
        =2              = (1,2)
        =3              = (1,3)
        =4              = (1,4)
 
N-1=3: i=5 → (a_i,b_i) = (2,1)
        =6              = (2,2)
        =7              = (2,3)
 
N-2=2: i=8 → (a_i,b_i) = (3,1)
        =9              = (3,2)
 
N-3=1: i=10 → (a_i,b_i) = (4,1)
 
我想問對於任何的正整數N, i€{1,..,S}
a_i跟b_i有沒有顯式公式 
(我知道電腦用loop逐次從N開始減, 還有剩就組數加1, 然後繼續減N-1
 直到即將減的下一個導致負數的時就知道是在當前這組
 但是我的需求是a_i與b_i的函數長相通式)
 
 
謝謝幫忙~
 
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.137.78 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1692291807.A.7EE.html
推 Vulpix      : a_i = ceil( N+0.5 - sqrt( (N+0.5)^2 - 2i ) )
→ Vulpix      : b_i = i - a_i( a_i - 1 )/2
 
哇V大這怎麼找的啊 這長相難怪我用線性的式都式不出來XDDD 好猛
 
推 Vulpix      : 就解不等式啊:)
→ Vulpix      : 你想想看 a_{k(k+1)/2} 是多少。
→ Vulpix      : 寫錯了，是 a_{k(2N-k+1)/2}。
 
b_i = i - a_i( a_i - 1 )/2
這個代入例子怪怪的? i=9時, a_i=3, b_i=2
但是 b_i = 2
     i - a_i( a_i - 1 )/2 = 9 - 3*2/2 = 6
不相等
 
我是得到 i=(2N-a_i+2)*(a_i-1)/2 + b_i這個等式然後想不到怎麼得到a_i或是b_i
 
剛剛由你說"不等式"以及看到ceil, 我寫出了:
 
(2N-k+2)*(k-1)/2 < i <= (2N-k+2)*(k-1)/2+N-k+1, 其中k就是a_i
 
該不會V大你姐的不等式就是這個吧...?
 
左邊跟右邊都是k的二次多項式P_L(k), P_R(k), 凹口向下
 
因此解P_L(k)=i的兩根為r_1<=r_2(假設為實根), 因此k<r1或是k>r2
同理解P_R(k)=i的兩根為r_3<=r_4(假設為實根), 因此r3<=k<=r4
 
是解這些東西嗎...@@?
※ 編輯: znmkhxrw (123.241.88.179 臺灣), 08/19/2023 03:19:41
推 Vulpix      : 所以是 b_i = i - a_i(2N-a_i+1)/2，前面寫錯了。
→ Vulpix      : b_i = i - (a_i-1)(2N-a_i+2)/2，前面又寫錯了。
→ Vulpix      : 那個……小的 r 應該都是負的。
了解~我再硬爆出來看看, 謝謝V大~
 
※ 編輯: znmkhxrw (123.241.88.179 臺灣), 08/24/2023 16:12:39