【数学】三进制的妙用

作者:万精油

这几天在网上流传一道趣味题。从形式看,我觉得是典型的竞赛题,没想到有人说这是上海某高中的考试题,而且是一道填空题。我个人认为如果以前没有见过这道题,要在考试时间内(假设为填这个空留用10分钟时间)解出这道题是相当不容易的。或许现在上海的高中生都很厉害?

解决这个问题的时候,发现一个三进制的妙用,决定把它写出来与大家分享。

原题:已知f的定义域和值域都是整数,并且单调递增。如果 f(f(n)) = 3n,问f(2017) = ?

解答:

先做一些观察:

1.       单调递增实际上是严格递增,就是说不同的数有不同的函数值,否则再一次函数映射后那个3倍就不知道倍哪个了。
2.     f(0) = 0, 如果不等于0,因为再映射一次要等于零,就破坏了单调递增。
3.     f(1) = 2,因为f(1)> 0, 从f(f(1)) = 3 可知f(1) 不能等于1, f(1) < 3
4.     f(2) = 3, 因为f(2) = f(f(1)).  类似的f(3)= 6,  f(6) = 9;
5.     3到6的区间映射到6到9区间,要保持单调递增,只能有f(4)=7,f(5)=8;
6.     从上面第5可以得到f(7) = 12, f(8) = 15, f(9) = 18;

有了上面的观测我们很容易验证下面这个性质:

推论1:对任意k, f(3^k) = 2 \times 3^k,f(2 \times 3^k)= 3^{k+1}

推论2: 类似于上面第5条,由于3^k2 \times 3^k 的区间映射到2 \times 3^k3^{k+1} 的区间,而两区间长度相同,要满足单调递增,函数值只能正好是原数加3^k。加3^k后的这些数(2 \times 3^k3^{k+1}的数)的函数值必须是3倍于减3^kk 后的那些数(上面第6条)。

对任意数x,我们可以把它表示成 x = c \times 3^k+r  (r < 3^k) 的形式, 其中c 只能等于1或2,从上面的推论可以得出,

c= 1 时,f(x) = x+3^k,c = 2 时,f(x) = 3 \times (x-3^k)

如果用MATLAB来写,上面的公式就对应于

k =floor(log(x)/log(3)) ;
c = floor(x/3^k);
y= (2*c-1)*(x + (3-2*c)*3^k);

比如,x =2017,  x = 2 \times 729+559 = 2 \times 3^6+559,从上面的公式我们有f(2017) = 3 \times (2017-3^6) = 3864.

本来,有了公式就可以结束了。但这道题的解都是在围绕那个3在转,如果用三进制,应该会有更自然的结果。我们不妨来试一试。

如果我们把一个数用三进制表示,那么,在 3^k2 \times 3^k  的那些数就是第一位数是1的那些数。我们的公式说,它们的函数值就是该数加 3^k ,也就是把第一位数从1变成2。在 2 \times 3^k3^{k+1} 之间的数在三进制下就是以2打头的数,它们的函数值是该数减 3^k  再乘3,也就是把第一位数变成1,整体向左平移一位(等于是乘3)。

归纳起来,我们有这样一个美妙结果

在三进制下,这个函数就是变一个首位数(或)加上平移。

例如:2017 = 2\times3^6+ 2 \times 3^5 + 0 \times 3^4 + 2 \times 3^3 + 2 \times 3^2 + 0 \times 3^1 + 1 = 2202201 (三进制)2打头,照上面的方法,把2换成1然后向左平移,得到12022010,这个数换成十进制就是 1 \times 3^7+2*3^6+0 \times 3^5+2 \times 3^4+2 \times 3^3+0 \times 3^2+1 \times 3^1+0= 3864

再比如,如果x = 1000,1000在三进制的表达是1101001,1打头,它的函数值就是把1变成2,得到2101001,换成十进制就是1729.

我以前给数学文化杂志写过一个关于三进制的文章叫【三生万物】,里面有论证说,从运算效率来说,三进制是计算机的最佳语言。

不过,电路0,1开关实在太方便,所以,二进制在现在的计算机中占了上风。随着科技发展,以后三进制计算机会逐渐占领主导地位的。文章里关于三进制的趣题例子是用天秤称乒乓球的,现在又多一个妙例,以后再写可以加进去。

结尾引一段高德纳(DonaldKnuth)关于三进制的话

“Perhaps the prettiest number system of all is the balanced ternary notation”  —- Donald Knuth

【游戏】益智数独挑战脑力
【人物】数学家丘成桐
【数学】美国普特南数学竞赛题(4)
【数学】美国普特南数学竞赛题(3)
【文摘】数学难题汇编(18)
【文摘】大学数学竞赛题汇编(15)
【文摘】趣味逻辑学问题(10)
【数学】彭罗斯镶嵌
【书籍】《皇帝的新脑》作者:罗杰.彭罗斯
【科普】为什么地球上的生物使用左旋的氨基酸和右旋的糖分子
【书籍】今日推荐《标竿人生Purpose Driven Life》
【文摘】阿尔法狗的上帝
【文摘】大学数学竞赛题汇编(10)
【人物】Conway: 游戏人生
【文摘】数学家俱乐部
【人物】凯利:真正成功的医生,不是为了赚钱
【视频】化蝶
【数学】3x+1问题(4)

此条目发表在数学分类目录,贴了, 标签。将固定链接加入收藏夹。