Rainer Rosenthal science forum Guru Wannabe
Joined: 29 Apr 2005
Posts: 114

Posted: Sun Jun 04, 2006 12:10 am Post subject:
Josephus climbing binary trees?



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 
