Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -


  • Please log in to reply
8 replies to this topic

#1 guru_bhai

guru_bhai

    Junior Member

  • Members
  • PipPip
  • 22 posts

Posted 14 April 2009 - 03:34 PM

1000 people are standing in a circle, all numbered from 1 to 1000.
Person 1 has sword with which he kills person 2 gives the sword to person 3.
Person 3 kills person 4 and passes the sword to person 5.
Every time the person who has the sword kills the next person in the circle and passes the sword.
This is continued till there is only one person alive.

Who is the Last Man Standing?


Spoiler for Answer :

  • 0

#2 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 14 April 2009 - 04:10 PM

Spoiler for my answer and my work

Unless I've done my bookkeeping wrong (that has happened sometimes...)

This is a specific case of the Josephus Ring, and I don't remember there being a closed form expression. However, with the example of skipping exactly one person, maybe there's a special case. (And, maybe I don't remember right)

Edited by CaptainEd, 14 April 2009 - 04:12 PM.

  • 0

#3 DeeDee1968

DeeDee1968

    Newbie

  • Members
  • Pip
  • 1 posts

Posted 14 April 2009 - 04:50 PM

Person 1 is left behind there would be no one to kill him
  • 0

#4 mghoffman78

mghoffman78

    Newbie

  • Members
  • Pip
  • 9 posts

Posted 14 April 2009 - 05:44 PM

Spoiler for my answer and my work

Unless I've done my bookkeeping wrong (that has happened sometimes...)

This is a specific case of the Josephus Ring, and I don't remember there being a closed form expression. However, with the example of skipping exactly one person, maybe there's a special case. (And, maybe I don't remember right)



I agree with CaptainEd.

Spoiler for Here is a general formula...

  • 0

#5 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 14 April 2009 - 06:28 PM

I agree with CaptainEd.

Spoiler for Here is a general formula...


MGH, that's Marvelous! Why/how does it work?
  • 0

#6 mghoffman78

mghoffman78

    Newbie

  • Members
  • Pip
  • 9 posts

Posted 14 April 2009 - 08:17 PM

MGH, that's Marvelous! Why/how does it work?


Not sure I can tell you exactly why it works but I can tell you how I came up with it. I started by looking for a pattern. First off, you find out real quick that the even people get waxed on the first round. I then checked the outcome for 1 to 20 people (it took a while). I noticed that when n (the total number of people) equals a power of 2 (i.e, 2, 4, 8, 16), then the first person is always the last man standing. Here is a list of the survivor for 1 to 20 people:

n survivor
1 1
2 1
3 3
4 1
5 3
6 5
7 7
8 1
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1
17 3
18 5
19 7
20 9

Once I saw this I was able to craft the "formula" to spit out the survivor based on any number of people. I wish I could say I used some clever method to get the formula, but I pretty much just kept looking till I found a way for it to work out.

If you look at it you do see that the formula does make sense. Take the case where n is a power of 2, say 16. On the first round of killings, all the even people are killed. You end up with a spacing of 2 in between all the survivors (i.e. 1,3,5,7,9...). Then after the second round, you end up with a spacing of 4 (1,5,9,13). Then after the third round you get a spacing of 8 (1,9). If we had used a very large power of 2 for n, then you would see that the spacings keep incrementing each round by a power of 2 (2,4,8,16,32,...). Also, if the total number of people is not a power of 2, then the spacings are still there, except there is an offset. I just used these patterns to come up with something that worked. I'm sure someone better at math could explain it better.

Mike
  • 0

#7 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1430 posts
  • Gender:Male

Posted 14 April 2009 - 09:21 PM

This is definitely not the most eloquent proof ever, but...
Spoiler for Proof of MGH's formula

  • 0

#8 guru_bhai

guru_bhai

    Junior Member

  • Members
  • PipPip
  • 22 posts

Posted 15 April 2009 - 01:02 AM

Congratulations guys you got it correctly .....


Spoiler for Complete solution

  • 0

#9 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1430 posts
  • Gender:Male

Posted 15 April 2009 - 01:16 AM

Congratulations guys you got it correctly .....


Spoiler for Complete solution


Neat! Much more elegant proof, hardly uses any math at all (which is a good thing).
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users