IBM 11月

constant · 发表于 2005-11-1 23:56:06

This month's puzzle concerns random binary trees. Let p be a fixed parameter between 0 and 1. Starting with the complete infinite binary tree retain each edge randomly and independently with probability p. Our random binary tree is the portion connected to the root. So for example the binary tree consisting of the root alone will be selected with probability (1-p)**2 (ie when neither edge out of the root is retained). www.ddhw.com

Some of these random binary trees will contain an infinite number of vertices. Throw these out. Then we ask what is the expected number of vertices as a function of p of a random binary tree selected in this way. This is a problem for which it is possible to obtain the right answer in a non-rigorous way. We will not attempt to check the derivation of submitted solutions but you should think about what would be required to prove your answer rigorously.

husonghu · 发表于 2005-11-2 00:26:13

You have been contributing nicely to this forum. 清儿 and I would like to invite you, seriously, to think about joining us as co-BanZhu now, or, sooner or later. In the future, we will have at least 3 co-BanZhus, and possibly 4, at any time, so each guy's duty will not be too heavy. Please think about this seriously. Thanks a lot, as always.

constant · 发表于 2005-11-2 00:50:36

Thanks a lot for your kind invitation. But I have to say that I cannot accept it, at least not now. As you can see I am not very patient. To be a qualified moderator one needs to be much nicer than I ever could be. Also as of now I have another job. Although I did not take it very seriously, it would still be a kind of conflicts of interest if I also work here.

I am also wondering why you asked me, since there is some one who is smarter and nicer.

QL · 发表于 2005-11-2 00:56:44

This seems easy by induction (sorry constant), some trap I didn't see?

L = p^2(1+2L)+2p(1-p)(1+L)+(1-p)^2,

L = 1/(1-2p)

constant · 发表于 2005-11-2 01:01:53

This is not exactly induction, but recursion. (And I love it .) I guess the trap is the expected number cannot be negative.

QL · 发表于 2005-11-2 01:05:33

I guess that means, for p>=1/2, the expected number of nodes is infinity.

constant · 发表于 2005-11-2 01:21:46

Yes

乱弹 · 发表于 2005-11-2 02:07:36

Yes, why not 野菜花？

野菜花 · 发表于 2005-11-2 03:23:43

因为 Hu 斑竹知道我从来不想当斑竹，WXC是这样，华闻的脑坛和基督人生论坛也都是这样，这也是我不如你们的地方，我的奉献精神远不如你们，所以我对你们都很佩服，也心存感谢，有时也会良心发现，来加一两把柴。另外我也知道我的能力很差, 这是真话，请你们原谅！

husonghu · 发表于 2005-11-2 03:35:33

You are all excellent candidates, much better than me. 野菜花 is not lacking of our invitation also.

Ah, ah, I wish some day you guys all can agree to join us. --- I'm looking forward to that day's coming.

Okay, constant, just bear in mind our invitation is valid indefinitely. Whenever you feel like accepting it, please just indicate so.

husonghu · 发表于 2005-11-2 07:22:36

重要意义是在于心理上的：
对原版主来说，有多一些“同伙”站在一起，心里踏实一些；
对众网友来说，有多一些领班，也比少一些领班更能鼓舞士气一些。
这个心理上的意义非常巨大：说“四两拔千斤”都不为过。

至于在“责任”和“奉献”上，实在没那么严重。更谈不上“能力”。你们看：
我这个版主的出题答题，远没如菜花，constant，Jenny等诸位多；
我做版主，再怎么努力，也比不上Jenny和ob的贡献；
即便我当初不做这个版主，在老版主们的领导下本坛也是可以发展的。

但是，我的站出来(继而是清儿的站出来)，“功不可没”哦！这个“功”就是对老版主们和对众网友的心理上的支持。

所以，我认为，只要站出来，这版主的“责任”和“奉献”就完成了50%以上了。

非常、非常、非常希望大家理解做版主的这一重意义；希望有越来越多的网友能自告奋勇加入co-版主的行列，不管你是老的，还是新的。你花“四两”力气，拔一个“千斤”，何不乐而为之呢？

寒潭清 · 发表于 2005-11-2 08:39:01

就是就是,偶举双手赞成HU班所言.也支持HU班的提议

野菜花 · 发表于 2005-11-2 19:18:14

我昨天没注意到 constant 的 post 里 "smart", "nice" 还有比较级，虽然我并不认为我是 "smart" "nice"，但别人说说也就算了，但 constant 说 "smarter" "nicer" 绝对不是指我，我在他的题目里出的洋相也够多的了。

constant · 发表于 2005-11-2 20:07:09

但是乱弹已经是WXC的坛主了。所以还是你最合适。 When I talk about being smart, I mean over all ability, not just solving some silly math problems. Even on that you are as good as anybody.

野菜花 · 发表于 2005-11-2 20:15:26

我地上挖个洞钻下去吧!

乱弹 · 发表于 2005-11-4 18:12:22

我做错你的题目也有好多次。而且我也来得少，既不 nice 又不 smart...

野菜花 · 发表于 2005-11-4 22:46:37

我怎么不记得你有做错的时候？

乱弹 · 发表于 2005-11-5 08:29:13

比如那个2N点问题，我当时还说找到了简单解法。。

还有很多错解没贴出来

野菜花 · 发表于 2005-11-5 19:30:19

没贴出来也算哪？

constant · 发表于 2005-11-7 18:11:47

我也有很多错解没贴出来。有时贴出来发现错了又删掉。

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

动态微博

IBM 11月

[@};-][@};-]An issue for constant to think about..

回复：[@};-][@};-]An issue for constant to think abou

回复：IBM 11月

回复：回复：IBM 11月

回复：回复：回复：IBM 11月

Yes

Yes, why not 野菜花？

回复：Yes, why not 野菜花？

You are all excellent candidates, much better ....

[:)][:)]再谈几句我自己的体会和感想。我觉得，做co-版主真的不是象菜花说得那么严重....

就是就是,偶举双手赞成HU班所言.也支持HU班的提议[:)]

我明白了，乱弹是故意转移目标。constant 明明是指你嘛！[:%]

Both of you qualify as smarter and nicer.

[:>][:>][:>]我地上挖个洞钻下去吧!

我做错你的题目也有好多次。而且我也来得少，既不 nice 又不 smart...

我怎么不记得你有做错的时候？[:O]

比如那个2N点问题，我当时还说找到了简单解法。。[:>]还有很多错解没贴出来

没贴出来也算哪？[:))][:))][:))]

我也有很多错解没贴出来。有时贴出来发现错了又删掉。[:>][:>]

动态微博

IBM 11月

[@};-][@};-]An issue for constant to think about..

回复：[@};-][@};-]An issue for constant to think abou

回复：IBM 11月

回复：回复：IBM 11月

回复：回复：回复：IBM 11月

Yes

Yes, why not 野菜花？

回复：Yes, why not 野菜花？

You are all excellent candidates, much better ....

[:)][:)]再谈几句我自己的体会和感想。我觉得，做co-版主真的不是象菜花说得那么严重....

就是就是,偶举双手赞成HU班所言.也支持HU班的提议[:)]

我明白了，乱弹是故意转移目标。constant 明明是指你嘛！[:%]

Both of you qualify as smarter and nicer.

[:>][:>][:>]我地上挖个洞钻下去吧!

我做错你的题目也有好多次。 而且我也来得少，既不 nice 又不 smart...

我怎么不记得你有做错的时候？[:O]

比如那个2N点问题，我当时还说找到了简单解法。。[:>]还有很多错解没贴出来

没贴出来也算哪？[:))][:))][:))]

我也有很多错解没贴出来。有时贴出来发现错了又删掉。[:>][:>]

我做错你的题目也有好多次。而且我也来得少，既不 nice 又不 smart...