小学生就能看懂，数学家却做不出来的３Ｘ＋１问题，你来试试？难[:%]

ob · 发表于 2005-11-12 01:06:05

任选一个整数，作下面的操作：

如果是奇数，把这个数乘3，然后加1
如果是偶数，把这个数除以2

然后把做完的结果重新作同样的操作，我们获得一个序列。

定理结论：这个序列最终会回到4－2－1上来。也就是说，不论原数大小，最终回到1。不过，过程有些是非常复杂的，有些数字跑回这个循环，可能经历很多次的颠簸。

乱弹 · 发表于 2005-11-12 02:21:22

谁解决了这个猜想，不说和哥猜的证明人一样有名，也至少上很多大报的头条了。

ob · 发表于 2005-11-12 02:29:47

行家一出手，就知有没有

yma16 · 发表于 2005-11-12 02:57:08

you are under 40.

husonghu · 发表于 2005-11-12 08:30:50

这位朋友显然是行家，见识广，欢迎你多显显身手啊！

Archi · 发表于 2005-11-13 03:08:10

Think of a Markov chain, with state space {1,2,...}. Notice that:

1) First verify that 1==>1, 4==>2==>1, 2==>1, therefore 1 is an absorbing state.
2) 4n ==> 2n, 4n+2 ==> 2n+1, they are absorbing states (become a smaller number);
3) 4n+1 ==> 3n+1, it is also an absorting state;
4) 4n-1 ==> 6n-1, with probability 0.5 to go to an absorbing state (4k+1). It is a transient state, with probability 1 to be absorbed.

From above, all states (all positive integers) will eventually be absorbed to 1.

Of course a formal proof can be more rigorous and will involve induction.

husonghu · 发表于 2005-11-13 03:54:55

欢迎你

很好的尝试。不过我有点看不懂，等其他各位来讨论吧！

流动的建筑 · 发表于 2005-11-14 03:59:38

For any positive integer n, define the operations:

F: F(n)=3n+1, n is odd, and
G: G(n)=n/2, n is even.

Now define a new operation H,
For n even, n=(2^k)*m, where m is odd, H(n)=G(..G(n)..)=m, and
For n odd, H(n) = F(n) = 3n+1.
Therefore, H(n) turns odd to even, and even to odd.

Now represent n in base 2, e.g., 43 ==> 101011. Notice that:

1) If n is even, H(n) removes the trailing zeros in n;
2) If n is odd, H(n)=3n+1=2n+n+1, where 2n is to add a trailing zero to n. We can verify that the number of 1's in H(n) is strictly decreasing. (By how many? I'll leave it as an exercise to you. A hint, think of XOR of neighboring bits.)
3) H(1)=100, H(100)=1.

It is clear now that for any positive integer n, in limited steps, the number of 1's in n will be reduced to 1. QED.

流动的建筑 · 发表于 2005-11-14 04:27:16

If n = 11...1 (all 1's), the number of 1's in H(n) equals that of n, but with a zero added as the second digit.

For any other odd number n, which has 0's in between 1's, the number of 1's in H(n) is strictly less than that of n.

QFT · 发表于 2005-11-14 06:14:56

what's the meaning of "XOR" in the sentence "think of XOR of neighboring bits."

QFT · 发表于 2005-11-14 06:29:34

If n is odd, H(n)=3n+1=2n+n+1, where 2n is to add a trailing zero to n. We can verify that the number of 1's in H(n) is strictly decreasing.

Seems not true;suppose n=1001001

then 2n = 10010010, n+1 = 1001010, and H(n) = 3n+1 = 11011100
so the number of 1's in H(n) increases in this case.

流动的建筑 · 发表于 2005-11-14 07:41:04

You are right. I should've considered it more carefully. But I believe the idea is correct.

In your case, we only need to apply H again.

A thorough proof probably needs much more work.

流动的建筑 · 发表于 2005-11-14 09:12:01

For any positive integer n, define the operations:

F: F(n)=3n+1, n is odd, and
G: G(n)=n/2, n is even.

Now define a new operation H,
For n even, n=(2^k)*m, where m is odd, H(n)=G(..G(n)..)=m, and
For n odd, H(n) = H(F(n)) = H(3n+1) = m, for some odd m.

Let's represent n in base 2, e.g., 43 ==> 101011.

For convenience, I will need two more functions:
B(n):= the number of bits of n. e.g. B(101011)=6.
W(n):= the trailing consecutive 1's in n, e.g. W(101011)=2, W(101000)=0.

1) When n is even, H(n) removes the trailing 0's from n. Clearly B(H(n)) < B(n).

2) When n is odd, there are W(n) trailing 1's in n. H(n) has the following properties:
2.1) If W(n) > 1, then B(H(n)) <= B(n), W(H(n))=W(n)-1;
2.2) If W(n)==1, then B(H(n)) < B(n).
In plain English, after each operation H, the number of bits will not increase, and the number of trailing 1's decrease by 1. When the number of trailing 1's is one, the next operation H will surely reduce the number of bits.

For any positive integer n, in limited steps, the number of bits will be reduced to 1. QED.

I thank QFT for pointing out my previous error.

ob · 发表于 2005-11-14 20:48:23

Surely deserve

yaluzangbu · 发表于 2005-11-14 23:53:36

2.1) If W(n) > 1, then B(H(n)) <= B(n)

It is wrong, e.g., 15 -> 23 -> 35.

流动的建筑 · 发表于 2005-11-15 01:34:30

You're right. I give up.

ob · 发表于 2005-11-15 09:43:05

Good Try!

		自动登录	找回密码
密码			立即注册

动态微博

小学生就能看懂，数学家却做不出来的３Ｘ＋１问题，你来试试？难[:%]

难度：++++++++++++++++++++++++++++++++++++++++++++++

行家一出手，就知有没有[@};-][@};-]

You can get the Fields award if you solve it and

这位朋友显然是行家，见识广，欢迎你多显显身手啊！[@};-][@};-]

试一试

欢迎你[@};-][@};-][@};-]很好的尝试。不过我有点看不懂，等其他各位来讨论吧！

上面的解法有漏洞，刚想到更好的方法

补充

回复：上面的解法有漏洞，刚想到更好的方法

one counter-example

回复：one counter-example

A complete proof

Surely deserve [@};-][@};-][@};-]

回复：A complete proof

You're right. I give up.

Good Try![@};-][@};-][@};-]