周末一题: "温一碗酒-十一文铜钱的故事"

无疆行者

本客按: 上次说到"周末一题: 喝酒不用'画蛇添足'", 又是周末了, 想起"十一文铜钱"的故事...

周末一题: "温一碗酒-十一文铜钱的故事"

"温一碗酒...", 他呐呐地说.

"要十一文钱呢", 声音从高高的柜台里面传出.

一颗头慢慢地升了起来, 一只手摊在柜台上.

手心里是一摞铜钱.

那手略斜着, 在台上微微滑动. 铜钱散落下来, 一个略压一个, 排成一线.

那手竟然倏地一翻, 铜钱依次翻了过来, 也是一线.

一望之下, 正是十一文.

...

时间过得很快. 一百年过去了-已经是公元2009年. 有好事者列题如下:

Let f: N->N be defined by

f(1) = 1
f(3) = 3

and, for all n∈N,

(a) f(2n) = f(n),
(b) f(4n+1) = 2f(2n+1) - f(n)
(c) f(4n+3) = 3f(2n+1) - 2f(n)

Find the number of n<=2009 for which f(n)=n.

NOTE: N, the set of positive integers 1, 2,3, ...

hanxin

行者，周末好！刚看到这题。还抓不到头脑。。。

hanxin

计算没问题，但是看不出规律来。

1967是在2009前最大的 n 。对吗？

hanxin

PALINDROME

是我把它们二进制写出后，一眼看出来的。即，所有f(n)=n， n's binary string is a palindrome。

反过来呢？是所有的两头为一的PALINDROME都包括在这个等式里了吗？

又是一个：一递归二进制！但这个比上周的shifting更高一层。

无疆行者

4# hanxin

呵呵, hanxin是手到擒来:) 下面得出最后的答案应该没有问题.

这回有个bonus题来问你, 能否证明你的观察?

hanxin

4# hanxin

呵呵, hanxin是手到擒来:) 下面得出最后的答案应该没有问题.

这回有个bonus题来问你, 能否证明你的观察?
无疆行者 发表于 2009-4-18 06:00 PM

这个太难了！有点无从下手。

上次你的证明我能看懂，但让我自己想，无论如何也想到你用的方法。

对称这个property怎样用递归的公式表示，I have no idea until today saw your puzzle。

我知道从 language processing 这个角度，palindromes 必须用 non-deterministic push-down automation 才能识别。但今天看了你这个函数，好像有点柳岸花明又一村的感觉。 证明的事，我想想。先去Gym。

hanxin

行者，我想了想，但没思路。只好缴枪了。

无疆行者

7# hanxin

为什么不试试以前的induction方法?

if define n as b[k]b[k-1]...b...b[1]b[0] (equivalent to b[k]*2^k+...+b[0]), b[k] = 1 as the leading bit, try to prove f(b[k]b[k-1]...b...b[1]b[0]) = b[0]b[1]...b...b[k-1]b[k]

hanxin

7# hanxin

为什么不试试以前的induction方法?

if define n as b[k]b[k-1]...b...b[1]b[0] (equivalent to b[k]*2^k+...+b[0]), b[k] = 1 as the leading bit, try to prove f(b[k]b[k-1]...b...b[1]b[0]) = b[0] ...
无疆行者 发表于 2009-4-20 12:08 AM

try to prove f(b[k]b[k-1]...b...b[1]b[0]) = b[0]b[1]...b...b[k-1]b[k]  

韩欣太笨！我还没能得到这个一般的 observation ！！！

我只看到， 当 f(n) = n 时， n 都是对称的。没想到竟是这样更一般的结果。怪我观察不细。那我试试吧。明天再来。

无疆行者

9# hanxin

思路在, 应该很容易了:)

hanxin

9# hanxin

思路在, 应该很容易了:)
无疆行者 发表于 2009-4-20 06:39 PM

今天忙，还没静下来想。不知道怎样用 那两个公式（b and c)。。。

hanxin

行者，我大致想了想，但没写下来。今天晚了，明天来。

hanxin

行者，今天终于能静下做作业。请看看对不。

Let f: N->N be defined by

f(1) = 1
f(3) = 3

and, for all n∈N,

(a) f(2n) = f(n),
(b) f(4n+1) = 2f(2n+1) - f(n)
(c) f(4n+3) = 3f(2n+1) - 2f(n)

n's binary = b[k]b[k-1]...b[2]b[1]b[0]  ( no leading zeros, i.e. b[k]=1)

Prove: f( b[k]b[k-1]...b[2]b[1]b[0] ) = b[0]b[1]b[2]......b[k-1]b[k]

1. Base cases (listing all cases for n =< 4)

f(1) = 1  
f(10) = f(1) = 1 = 01
f(11) = 11
f(100) = f(10) = f(1) = 1 = 001

2. Induction

Assume for all positive integers less than n the above equality holds, prove it is true for n

n's binary = b[k]b[k-1]....b[2]b[1]b[0]

case 1 - if n is even, then b[0] = 0, and n = 2*m
where m's binary = b[k]b[k-1]....b[2]b[1]

from   f(n) = f(2m) = f(m) and m<n, we get
f(b[k]b[k-1]....b[2]b[1]b[0]) =    (using (a))
f(b[k]b[k-1]....b[2]b[1]) =  
b[1]b[2]...b[k-1]b[k] =
0b[1]b[2]...b[k-1]b[k] =
b[0]b[1]b[2]...b[k-1]b[k] (as we know b[0]=0)

case 2 - if n is odd and n = 4m+1

m's binary = b[k]b[k-1]...[b2] , and we know that b[1]=0, b[0]=1

from f(4m+1) = 2f(2m+1) - f(m) we have
f(b[k]b[k-1]....b[2]b[1]b[0]) = 2f(b[k]b[k-1]...b[2]1) - f(b[k]b[k-1]...b[2]) =
2*(1b[2]...b[k-1]b[k] - [b2]...b[k-1]b[k] =    (using induction)
1b[2]...b[k-1]b[k] - [b2]0 - b[2]...b[k-1]b[k] =  (I jumped a bit here, but it is  easy to prove it)
10b[2]...b[k-1]b[k] =
b[0]b[1]b[2]...b[k-1]b[k]

case 3 - if n is odd and n = 4m+3

m's binary = b[k]b[k-1]...[b2] , and we know that b[1]=1, b[0]=1

from f(4m+3) = 3f(2m+1) - 2f(m) we have

f(b[k]b[k-1]....b[2]b[1]b[0]) = 3f(b[k]b[k-1]...b[2]1) - 2f(b[k]b[k-1]...b[2]) =
3*(1b[2]...b[k-1]b[k] - 2*( [b2]...b[k-1]b[k]) =    (using induction)
2*(1b[2]...b[k-1]b[k] - 2*( [b2]...b[k-1]b[k]) + 1b[2]...b[k-1]b[k] =
10000...00 (k zeros) + 1b[2]...b[k-1]b[k] =
11b[2]...b[k-1]b[k] =
b[0]b[1]b[2]...b[k-1]b[k]

[]

无疆行者

13# hanxin

呵呵, 除了几个下标等小问题, 思路基本在:)

Also for case 2

#DD: close the gap of "jumped a bit"...

1b[2]b[3]...b...b[k-1]b[k]0 - f(m) =
2^K + b[2]b[3]...b...b[k-1]b[k]0 - f(m) =
2^K + 2f(m) - f(m) =
2^K + f(m) =
2^K + b[2]b[3]...b...b[k-1]b[k] =
10b[2]...b[k-1]b[k] =
b[0]b[1]b[2]...b[k-1]b[k]

Is it your thought?

For case 3

2*(1b[2]...b[k-1]b[k] - 2*( [b2]...b[k-1]b[k]) + 1b[2]...b[k-1]b[k] =
2*2^(k-1) + 1b[2]...b[k-1]b[k] =
2^K + 1b[2]...b[k-1]b[k] =
11b[2]...b[k-1]b[k] =
b[0]b[1]b[2]...b[k-1]b[k]

无疆行者

这里不是数学竞赛, 呵呵, 不需要非常严格的证明-思路在就可以了. 但是最关键的:

Find the number of n<=2009 for which f(n)=n还没得出呢?

hanxin

这里不是数学竞赛, 呵呵, 不需要非常严格的证明-思路在就可以了. 但是最关键的:

Find the number of n
无疆行者 发表于 2009-4-23 11:57 PM

我在第三楼说的，1967，不对吗？这是最大的，还有好多。只要对称就行。

hanxin

13# hanxin

呵呵, 除了几个下标等小问题, 思路基本在:)

Also for case 2

#DD: close the gap of "jumped a bit"...

1b[2]b[3]...b...b[k-1]b[k]0 - f(m) =
2^K + b[2]b[3]...b...b[k-1]b[k]0 - f(m) =
2^K +  ...
无疆行者 发表于 2009-4-23 11:54 PM

谢谢批改！

case 3, 我那个 100...00 （k zeros） 太不正规

思路对了？好好，那自己也高兴一番。

hanxin

突然想，你是不是问一共有多少？

用程序算了算一共92个。

f(1) = 1 1
f(3) = 3 11
f(5) = 5 101
f(7) = 7 111
f(9) = 9 1001
f(15) = 15 1111
f(17) = 17 10001
f(21) = 21 10101
f(27) = 27 11011
f(31) = 31 11111
f(33) = 33 100001
f(45) = 45 101101
f(51) = 51 110011
f(63) = 63 111111
f(65) = 65 1000001
f(73) = 73 1001001
f(85) = 85 1010101
f(93) = 93 1011101
f(99) = 99 1100011
f(107) = 107 1101011
f(119) = 119 1110111
f(127) = 127 1111111
f(129) = 129 10000001
f(153) = 153 10011001
f(165) = 165 10100101
f(189) = 189 10111101
f(195) = 195 11000011
f(219) = 219 11011011
f(231) = 231 11100111
f(255) = 255 11111111
f(257) = 257 100000001
f(273) = 273 100010001
f(297) = 297 100101001
f(313) = 313 100111001
f(325) = 325 101000101
f(341) = 341 101010101
f(365) = 365 101101101
f(381) = 381 101111101
f(387) = 387 110000011
f(403) = 403 110010011
f(427) = 427 110101011
f(443) = 443 110111011
f(455) = 455 111000111
f(471) = 471 111010111
f(495) = 495 111101111
f(511) = 511 111111111
f(513) = 513 1000000001
f(561) = 561 1000110001
f(585) = 585 1001001001
f(633) = 633 1001111001
f(645) = 645 1010000101
f(693) = 693 1010110101
f(717) = 717 1011001101
f(765) = 765 1011111101
f(771) = 771 1100000011
f(819) = 819 1100110011
f(843) = 843 1101001011
f(891) = 891 1101111011
f(903) = 903 1110000111
f(951) = 951 1110110111
f(975) = 975 1111001111
f(1023) = 1023 1111111111
f(1025) = 1025 10000000001
f(1057) = 1057 10000100001
f(1105) = 1105 10001010001
f(1137) = 1137 10001110001
f(1161) = 1161 10010001001
f(1193) = 1193 10010101001
f(1241) = 1241 10011011001
f(1273) = 1273 10011111001
f(1285) = 1285 10100000101
f(1317) = 1317 10100100101
f(1365) = 1365 10101010101
f(1397) = 1397 10101110101
f(1421) = 1421 10110001101
f(1453) = 1453 10110101101
f(1501) = 1501 10111011101
f(1533) = 1533 10111111101
f(1539) = 1539 11000000011
f(1571) = 1571 11000100011
f(1619) = 1619 11001010011
f(1651) = 1651 11001110011
f(1675) = 1675 11010001011
f(1707) = 1707 11010101011
f(1755) = 1755 11011011011
f(1787) = 1787 11011111011
f(1799) = 1799 11100000111
f(1831) = 1831 11100100111
f(1879) = 1879 11101010111
f(1911) = 1911 11101110111
f(1935) = 1935 11110001111
f(1967) = 1967 11110101111
done
total 92

无疆行者

18# hanxin

呵呵, 正是92

本意是要推导的:

k (k+1) bits E.Q.
0     1        1   // 1
1     2        1   // 11
2     3        2   // 101, 111
3     4        2   // 1001, 1111
4     5        4   // 10001, 11011, 10101, 11111
5     6        4   // 100001, 110011, 111111, 101101

k even (--x--): <(k+1)><k...k/2+2><(k+1+1)/2><k/2...2><1>, 2*2^(k/2 - 1) = 2^(k/2)
k odd (----): <(k+1)><k...(k+1)/2+1><(k+1)/2...2><1>, 2^((k+1)/2 - 1) = 2^((k-1)/2)

(2009)[10] = (11111011001)[2]

n>2009 only having two to meet:
...
(2015)[10] = (11111011111)[2]
...
(2047)[10] = (11111111111)[2]

k = 10, 2^5
k = 9, 2^4
k = 8, 2^4
k = 7, 2^3
k = 6, 2^3
k = 5, 2^2
k = 4, 2^2
k = 3, 2^1
k = 2, 2^1
k = 1, 2^0
k = 0, 2^0

Thus the number of n<=2009 for which f(n)=n:

2*(2^0+2^1+2^2+2^3+2^4) + 2^5 - 2 = 2*(2^5-1)+2^5 -2 = 3*2^5 - 4 = 92

无疆行者

这条线就关了吧, 再会!

hanxin

这条线就关了吧, 再会!
无疆行者 发表于 2009-4-24 02:42 PM

不好意思，韩欣又犯老毛病。看了你算的，才后悔为什末自己没去算。写了一辈子程序，本性难移。

不过，开始我没明白你是问一共有多少。。。 怪我读贴不仔细。

hanxin

这周末没题？

无疆行者

这周末没题？
hanxin 发表于 2009-4-26 01:38 PM

呵呵, 昨天忙了一整天, 没功夫事先验算.

一会儿回来再重开一线:)