FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Recreational
Josephus climbing binary trees?
Post new topic   Reply to topic Page 1 of 1 [1 Post] View previous topic :: View next topic
Author Message
Rainer Rosenthal
science forum Guru Wannabe


Joined: 29 Apr 2005
Posts: 114

PostPosted: Sun Jun 04, 2006 12:10 am    Post subject: Josephus climbing binary trees? Reply with quote

Please have a look into Neill Sloanes wonderful world
of integer sequences:
http://www.research.att.com/~njas/sequences/A112088
This sequence gives the

"Number of leaf nodes in a binary tree"(*)


Playing the "Josephus problem" with "every third out",
I realized that the numbers of this sequence, i.e.
2, 3, 5, 7, 11, 16, 24, 36, 54, 81, 122, 183, 274, 411
show up as minimum numbers in the game(**).

The minimum number of children needed to play 6 rounds
is just 16. And for 7 rounds you need at least 24 etc.

As an example I will show the 3 rounds, which can be played
with 5 children (fixed size font needed):

1^ 2 1 2 . 2^
5 3 --> 5 . --> 5 . first round
4 4^ 4

. 2^ . 2^
5 . --> . . second round
4 4

. 2^ . .
. . --> . . third round
4 4^

Now only one child is left, the game ends after 3 rounds, if
5 children are in the circle at start. With 4 children there
are ownly two rounds possible.

(*) Whatever that means. But it sounds important.
The resemblance with a(n) = floor(sqrt(2)*(3/2)^n), i.e.
http://www.research.att.com/~njas/sequences/A033320
was stunning too but experts will surely know.

(**) I checked that for the first 18 members, which makes
my discovery quite probable but doesn't prove anything. But
may be some proof will be given in the course of the
(hopefully starting) recreational discussion.

Best regards,
Rainer Rosenthal
r.rosenthal@web.de
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [1 Post] View previous topic :: View next topic
The time now is Fri Nov 17, 2017 5:22 pm | All times are GMT
Forum index » Science and Technology » Math » Recreational
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Solving a large-scale sparse almost binary linear system ... Susan Margulies Research 0 Thu Jun 29, 2006 1:15 am
No new posts Solving large-scale sparse binary linear systems EXACTLY? Susan Margulies num-analysis 9 Wed Jun 28, 2006 6:41 pm
No new posts binary relations Stefan Ram Math 5 Mon Jun 19, 2006 5:03 am
No new posts Drawing automata/trees un student Undergraduate 1 Thu Jun 15, 2006 11:21 am
No new posts regarding the correlation of two binary matrices liav.ezer@gmail.com Math 0 Mon May 22, 2006 3:27 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0712s ][ Queries: 16 (0.0547s) ][ GZIP on - Debug on ]