一道編程/數學挑戰題，應如何思考？

12-03

我寫個簡單點的步驟

記數列 $a_0 = 1$ ， $a_{n+1} = f(a_n)$

則 $a_{n+2} = f(f(a_n)) = 3a_n$

因為 $f(a_1) = 3$ ， $f(1) = a_1$ ，所以 $a_1 e 1$ 且 $a_1 < 3$ ，所以 $a_1 = 2$

所以

$f(3^k) = 2cdot 3^k$

$f(2cdot 3^k) = 3^{k+1}$

注意到 $3^{k+1} - 2cdot 3^k = 2cdot 3^k - 3^k$ ，源區間和目標區間一樣大，再根據單調性必然有

$f(3^k + m) = 2cdot 3^k + m (0 le m le 3^k)$

因此有

$f(2 cdot 3^k + m) = f(f(3^k + m)) = 3^{k+1} + 3m (0 le m le 3^k)$

要求的 $2017 = 2cdot 3^6 + 559$ 因此 $f(2017) = 3^7 + 3 cdot 559 = 3864$

話說我怎麼感覺這題我答過呢

顯然f(n)不能等於n，否則f(f(n))=n&<3n；另外，由於f(n)嚴格遞增，值域又是正整數，因此f(n)&>n。

於是f(1)不能等於1，也不能等於3（否則f(3)=3），也不能大於3，只能是f(1)=2，f(2)=3。

又注意到，f(3n) = f(f(f(n))) = 3f(n)

觀察到：如果f(k)=p, f(k+1)=p+1，則

f(3k) = 3p, f(3k+3) = 3p+3

於是 f(3k+1) = 3p+1, f(3k+2) = 3p+2

此時3k~3k+3的取值正好是3p~3p+3，於是進一步地9k~9k+9的取值也必須是9p~9p+9，依此類推。

因為f(1)=2, f(2)=3，於是

1~2 取值為 2~3

3~6 取值為 6~9

9~18 取值為 18~27

27~54 取值為 54~81

81~162 取值為 162~243

243~486 取值為 486~729

729~1458 取值為 1458~2187

倒推出2017=2187-170=f(1458-170)=f(1288)

f(2017) = f(f(1288)) = 3864

實際上我們可以寫出通項公式：

n可以唯一表示成n=a*3^k+p的形式，其中k&>=0，a=1或2，0&<=p&<3^k。

若a=1，n=3^k+p，f(n)=f(3^k+p)=f(3^k)+p=2*3^k+p

若a=2，n=2*3^k+p，倒推出f(3^k+p)=n，f(n)=3(3^k+p)

檢查各項條件：

1）定義域和值域顯然都是正整數

2）嚴格遞增只需檢查

f(3^k-1)=f(2*3^(k-1)+3^(k-1)-1)=3(3^(k-1)+3^(k-1)-1)=2*3^k-3&<2*3^k=f(3^k)

f(2*3^k-1)=f(3^k+3^k-1) = 2*3^k+3^k-1 = 3^(k+1)-1&<3^(k+1)=f(2*3^k)

3）分兩種情況

f(f(3^k+p)) = f(2*3^k+p) = 3(3^k+p)

f(f(2*3^k+p)) = f(3(3^k+p)) = f(3^(k+1)+3p) = 2*3^(k+1)+3p = 3(2*3^k+p)

我怎麼在數學競賽上見過一模一樣的呢？就是最後f(2017）在競賽上是f（100）。請問這個六年級小女孩是哪一年出的題？題主又是怎麼知道的？

附上競賽答案

這道題我很有印象，想起來這是一試書上的題，懶得再寫一遍過程了，找出書來給題主看一下吧(??????) ?（第11題喲）

我比較笨，沒有找出那麼通項的解，而是找到了一個遞推的式子，通過寫程序還是得出了答案。

先放結論： $f(2017)=3864$

$f(a)= left { egin{array}{rcl} 3f(n) mbox{for} a = 3n \ 3f(n) + b mbox{for} a = 3n + b, f(n+1) - f(n) = 1 \ 3f(n)+3b mbox{for} a = 3n + b, f(n+1) - f(n) = 3 end{array} ight.$

此處 $0<b<3$

而且這個數列也被OEIS收錄過了：A003605 - OEIS

然後說我的思路：

引理1：單射性質，即 $f(a)=f(b) Rightarrow a = b$

根據 $f(x) < f(x + 1)$

$a < b Rightarrow f(a) < f(b), b < a Rightarrow f(b) < f(a)$

引理2： $f(3x) = 3f(x)$

根據引理1，有

$f(3x) = f(f(f(x)))$

進而 $f(f(f(x))) = 3f(x)$

推論1：

$f(x + 1) - f(x) leq 3$

假設有一個 $x$ 滿足 $f(x+1) - f(x) > 3$ ，則根據鴿籠原理，必然有一個 $y$ 使得 $f(x)<3y<f(x+1)$ ，

則 $x<f(y)<x+1$ ，但是 $x$ 和 $x+1$ 之間沒有整數了，所以我們發現沒有這麼一個 $x$ 。

先找出 $f(1)$ 的值：

設 $f(1)=a$ ，首先 $f(1) e 1$ ，接著有

$1 < f(1) < f(a) = 3 Rightarrow f(1) = 2, f(2) = 3$

對 $a=3n$ 的證明其實就是引理2，接下來證明 $a=3n+b$ 的情況。

先假設 $f(x+1) - f(x) e 2$ ，經檢驗發現對於 $f(2)-f(1)=3-2=1 e 2$ 成立。

對於一組 $3n < 3n + 1 < 3n + 2 < 3(n + 1)$ ，有 $f(3n) < f(3n + 1) < f(3n + 2) < f(3(n+1))$ ，進而有 $3f(n) < f(3n + 1) < f(3n + 2) < 3f(n + 1)$ 。

又因為 $3(f(n+1) - f(n)) in {3 imes 1 = 3,3 imes 3 = 9}$ ，

如果 $3(f(n+1)-f(n)) = 3$ ，那麼中間兩數只能是 $f(3n+1) = 3f(n) + 1, f(3n + 2) + 3f(n) + 2$ 。

如果 $3(f(n+1)-f(n)) = 9$ ，那麼因為相鄰兩數差必須小於等於3，所以只能是 $f(3n+1) = 3f(n) + 3, f(3n + 2) = 3f(n) + 6$ 。

對於前者情況，兩兩數的差為1，後者則為3， $f(x+1) - f(x) e 2$ 仍然沒有被破壞。

所以我們可以得出結論：

$f(a)= left { egin{array}{rcl} 3f(n) mbox{for} a = 3n \ 3f(n) + b mbox{for} a = 3n + b, f(n+1) - f(n) = 1 \ 3f(n)+3b mbox{for} a = 3n + b, f(n+1) - f(n) = 3 end{array} ight.$

寫成C++程序：

#include &


using namespace std;
const int N = 2017;
int a[N + 1];

int main() { int x, y; a[1] = 2; a[2] = 3; for (int i = 3; i &<= N; ++i) if (i % 3 == 0) a[i] = a[i / 3] * 3; else { x = a[i / 3]; y = a[i / 3 + 1]; a[i] = x * 3 + (y - x) * (i % 3); } printf("%d ", a[N]); return 0; }

輸出結果：3864

1，f(f(n))=3n。
則f(3n)=f(f(f(n)))=3f(n)，
則f(3^k.n)=3^k.f(n)。
2，f(n+1)＞f(n)≥1。
f(3)=3f(1)。
f(f(1))=3，如果f(1)≥3，
則f(f(1))＞f(1)≥3，矛盾，故f(1)＜3。
又f(1)=1時，f(f(1))=3=f(1)，矛盾。
故f(1)=2。f(2)=f(f(1))=3，
f(3)=3f(1)=6，
f(3^k)=3^k.f(1)，
f(3^(k+1))=3^(k+1).f(1)，
f(2.3^k)=3^k.f(2)。
則有
(1)，2.3^k-3^k=3^k，
3^k.f(2)-3^k.f(1)=3^k。所以在[3^k，2.3^k]，
f(n+1)=f(n)+1。
所以在在[3^k，2.3^k]，
f(3^k+m)=f(3^k)+m=2.3^k+m。
(2)，3^(k+1)-2.3^k=3^k，
3^(k+1)f(1)-3^k.f(2)=3^(k+1)=3.3^k，
所以在[2.3^k，3^(k+1)]，
f(n+1)=f(n)+3。
f(2.3^k+m)=3^(k+1)+3m。
2.3^6＜2017＜3^7，2.3^6=1458，故使用公式二。k=6，m=2017-1458=559，
f(2017)=3^7+599.3=2187+1677=3864。

設f(1)=x，則f(x)=3，首先可以得出：x&>1，然後由於f(3)=3x，所以f(2)是x和3x之間，接下來f(3x)=3*3=9，由於遞增，則9-x&>=3x-1，解得x&<=2.5，所以x只能是2，所以這個序列就推出來了

挺有意思的一道題，真的是老了，想了半天才想明白，總結如下：

設 f(1)=y，則f(y)=3。

因為值域為正整數，可得y&>=1，當 y=1時，f(1) =1, f(1)=3 矛盾，所以 y &> 1.

又有f(n)&1, 所以 f(y) &> f(1), 即3&>y.

由 1&

令 f(x) = m, 則f(m) = 3x，則f(3x) = 3m = 3f(x)

很顯然這是個遞歸，即f(9x) = 3f(3x) = 3*(3f(x)) = 9f(x)

所以有 $f(3^{n} x) = 3^{n}f(x)$ , 當x = 1時，即存在 $f(3^{n}) = 3^{n}f(1) = 2* 3^{n}$

再次運用 f(x) = m 時 f(m) = 3x公式，得到 $f(2* 3^{n}) = 3* 3^{n}$ .(n為非負整數)

即定義域在 $[3^{n}, 2* 3^{n} ]$ 範圍內，值域為 $[2*3^{n}, 3* 3^{n} ]$ ，且函數單調遞增，定義域和值域均為正整數，所以可以確定 $f(3^{n} + m) = 2*3^{n} + m$ ( $0 leq mleq3^{n}$ )

但這個時候定義域不夠全，缺少 $[2*3^{n}, 3* 3^{n} ]$ 部分，怎麼辦呢，再用一次當f(x) = m 時 f(m) = 3x公式。得到 $f(2*3^{n} + m) = 3*3^{n} + 3m$ ( $0 leq mleq3^{n}$ )

匯總就是：

當定義域為 $[3^{n}, 2* 3^{n} ]$ 時，即 $x = 3^{n} + m$ （ $0 leq mleq3^{n}$ ，n為非負整數）

$f(x) = 2*3^{n} + m = 3^{n} + x$

當定義域為 $[2*3^{n}, 3* 3^{n}]$ ，即 $x = 2*3^{n} + m$ （ $0 leq mleq3^{n}$ ，n為非負整數）

$f(x) = 3*3^{n} +3m = 3x - 3^{n+1}$

即：

n為非負整數

x = 2017, 即n = 6，定義域在第二組內，則 $f(2017) = 3 imes2017-3^{7} = 3864$

以上！

利用Matlab做出的f（x）圖像如下

f（2017）=3864

代碼

clear all

x=[1:5000]

y=zeros(size(x))

y(1)=2

y(2)=3

for i=1:5000

for j=1:5000

if j==y(i)

y(j)=3*i

continue

end

for i=1:5000

for j=i+2:5000

if y(j)-y(i)==j-i y(j)~=0 y(i)~=0 y(j-1)==0

for k=1:j-i-1

y(i+k)=y(i)+k

end

i=j

continue

end

for i=1:5000

for j=1:5000

if j==y(i)

y(j)=3*i

continue

end

plot(x,y)

先從小的數試起。

首先，由（1）我們能得到$f(n)$大於等於$n$，由（2）又能得出$f(n)$不能等於$n$。所以$f(n)$大於$n$。

那麼1小於$f(n)$小於$f(f(n))$，所以$f(1)$為2。由（2），我們可以迭代出f(2 imes 3^n)=3^(n+1),f(3^n)=2 imes 3^n。而3^(n+1)與2 imes 3^(n+1)中間點數與f(3^(n+1))與f(2 imes 3^(n+1))中間的數一樣多，那麼根據f的嚴格性，中間的函數值就被唯一確定了。

具體的，1458小於2017小於2187，2017-1458=559，所以f(2017)=f(1458)+559=2187+559=2746

儘可能的簡單。

因為 $f(n) < f(n + 1)$ ，而且域和值域都是正整數，我們就先從1開始一步步推導：

如果 $f(1) = 1$ ，則根據 $f(f(n)) = 3n$ ， $f(1) = 3$ ，不對。

如果 $f(1) = 2$ ，則 $f(2) = 3$ ，OK！

如果 $f(1) = 3$ ，則 $f(3) = 3$ ，根據遞增性，不對。而且 $f(1)$ 取比3大的值則明顯不對了。

所以有 $f(1) = 2，f(2) = 3$ 。繼續推導：

$f(3) = 6$ ... $f(6) = 9$

$f(9) = 18$ ... $f(18) = 27$

$f(27) = 54$ ... $f(54) = 81$

......

由此可見，我們只需找出2017落的範圍，就能求出 $f(2017)$ 。寫一段Java代碼來實現。注意，needle可能落在左邊，也可能落在右邊。

/** * Maskman */ public class Maskman { public static int f2017(int needle) { int lowIndex = 1; int highIndex = 2; int lowValue = 2; int highValue = 3; final int factor = 3;

while (true) { if (needle &>= lowIndex needle &<= highIndex) { return lowValue + (needle - lowIndex); } else if (needle &>= lowValue needle &<= highValue) { return (lowIndex + (needle - lowValue)) * 3; } else { lowIndex *= factor; highIndex *= factor; lowValue *= factor; highValue *= factor; } } } public static void main(String[] args) { System.out.println(f2017(2017)); // 3864 } }

同步在了我的知乎專欄（2gua的編程生活）。

詳細描述可以看Richard Xu那一條回答

注意一下每行黃色重複時候n的值。當n屬於3^a~3^a*2時，定義域的整數取值有3^a個；

f（n）取值也正好為3^a*2~3^a*3，正好能塞下3^a個連續自然數

所以稍微不嚴謹點的描述

當n取值在3的相鄰兩個整數冪之間時

前半段的f（n）值為連續自然數，從2n取到3n；

後半段中，n正好被是前半段f（n）的值覆蓋，還是連續的整數

所以f（n）的取值是2n*3~3n*3的等差數列

3^6=729，3^7=2187,中間值是1458

前半段為：n取729~1458的連續自然數，f（n）值是1458~2187

已經涵蓋了2017，對應的f（1288）=2017

最終f（2017）=f（f（1288））=3864了。

很老很經典的題了，但是描述不對，一般都寫作 N*–&>N*的映射

說句暴露年齡的話，這題十一年前做過，也就是很可能比小女孩年齡大

python 3

a = [i+1 for i in range(0,2018)] alpha,beta=[2,3] for i in range(3,2018): if i%3 == 0: a[i] = a[i//3]*3 else: alpha = a[i//3] beta = a[i//3+1] a[i] = alpha*3+(beta-alpha)*(i%3) print(a[2017])

》》》3864

a = [i+1 for i in range(0,2018)] alpha,beta=[2,3] for i in range(3,2018): if i%3 == 0: a[i] = a[i//3]*3 else: alpha = a[i//3] beta = a[i//3+1] a[i] = alpha*3+(beta-alpha)*(i%3) for i in range(1,2018): print(a[i])

》》》2

》》》3

》》》6

......

》》》3864

rua～～～

rua

def r_set(x):

r={}

for idx, value in x.items():

r[value]=idx

return r

def sub_v(i,sets):

g=None

for i_0 in range(3,i):

d=3*i_0-sets[i-1]

if d&>0:

if g==None:

g=d

r=i_0

else:

if d&

g=d

r=i_0

return r

def Nsets(x):

sets={}

sets[1]=2

if x == 1:

return sets[x]

else:

for i in range(2,x+1):

setr=r_set(sets)

if i in setr:

sets[i]=3*setr[i]

else:

if sub_v(i,sets)*3+i-1==sets[sub_v(i,sets)]+sets[i-1]:

sets[i]=sets[i-1]+1

else:

return i

print("rua!")

break

return sets[x]

Nsets(2017)

Output=3864

這個挺有意思。
關鍵在於正整數，下面這一段是我的簡易分析：

依此可以不斷後推。可以預見的是，2017不是3的倍數，因此f(2017)肯定是卡在某兩個數之間，其值應該會有多解(嘗試找出擬合關係的做法都是不合理的，因為依條件只能得到某些特殊點與點之間的映射，被避開的點取值只要滿足遞增就夠了)。如有疏漏，敬請指正。

同感此題做過……

f(0)可以等於0,那麼看f(1)。顯然f(1)不能等於1，否則f(f(1))=f(1)=1，與f(f(1))=3矛盾；若f(1)≥3，則根據嚴格遞增性，f(f(1))≥f(3)&>f(1)≥3，即f(f(1))&>3，與f(f(1))=3矛盾；所以只能f(1)=2。

那麼可以得出f(2)=f(f(1))=3，f(3)=f(f(2))=6，f(6)=f(f(3))=9，依此類推

f(1)=2；f(2)=3； f(3)=6；f(6)=9；f(9)=18；f(18)=27；f(27)=54；f(54)=81；f(81)=162；f(162)=243； f(243)=486； f(486)=729……

中間有一些被跳過的項，可以由題中嚴格單增的條件結合條件3得出，如f(3)=6，f(6)=9，可以得出f(4)=7，f(5)=8，進一步可以得出f(7)=12，f(8)=15，這樣可以得出全部的函數值。

下面直接跳到f(729)=1458，f(1458)=2189，由於1458-729=729，2189-1458=729，可得到f(729+k)=1458+k，其中0&

f(2016)=f(f(1287))=3861，

f(2017)=f(f(1288))=3864。

題主表示早已經AC了這道題，就是發出來看看大家的方法，附上我寫的的代碼

我自己硬推了一遍之後算是把規律做出來了，但是表述太繁複。後來我找到了一個取巧的辦法，非常好描述：

第一步：把n表達為三進位

第二部：如果n最高位為1,則f(n)就是最高位改2。如果n最高位為2，那麼f(n)就是 n*10 然後把最高位改1。

貼個圖：

這個想法有個附帶效果：如果題目改一個條件：f(f(f(n)))=4n, 也有解：
首先，把n表達為4進位...

以下是不嚴謹的推論：

由f(y) = 3x; f(x)=y;可得：

f(1) = y"; f(y") = 3;

假設y"=1則有f(1) = 1; f(1) = 3;不符合單調遞增，所以y"&>1

假設y"&>=3則有f(1) &>= f(y") ;同樣與單調遞增矛盾，所以y"&<3

所以y"=2;

f(1) = 2; f(2) = 3;

好的，開始編程

int calc(int n) { using std::vector; vector& yArray{-1, 2, 3}; for (int i = 3; i &<= n; i++) { auto finded = std::find(yArray.begin(), yArray.end(), i); if (finded != yArray.end()) { yArray.push_back((finded - yArray.begin())*3); } else { yArray.push_back(yArray.back()+1); } } int y = yArray[n]; return y; } calc(2017);