Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

KingGeorge Group Title

[UNSOLVED, ANSWER GIVEN] KingGeorge's Challenge of the Month Suppose you have \(n\) children sitting in a circle waiting for Santa to give each of them one present. When Santa finally arrives, he announces he'll pass out the presents in such a way that he'll go in a clockwise circle, and give a present to every other child who has not yet received a present starting with the second child. Find a closed formula to find which child got the \(n-1\)-th present. If, say, there were 6 children in a circle, the order in which they would get presents is 2, 4, 6, 3, 1, 5. So the 1st child got the \(6-1\)-th present.

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I should say that this is a rather difficult problem. I've also changed the wording so you can't google a solution. And even if you did manage to google the original problem, the one formula I found online for this, was incorrect.

    • 2 years ago
  2. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Also, if you want me to compute some test values for you, let me know what \(n\) to use.

    • 2 years ago
  3. joemath314159 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    im getting something like: let n be\[n=3\cdot 2^k+r,0\le r\le 3\cdot 2^k\]Then the answer is:\[2r+1\]Havent written out a proof yet though >.<

    • 2 years ago
  4. FoolForMath Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    This is a variation of Extended Josephus problem, where \( x=n-1 \) The recursive and the non-recursive formulas are discussed here: http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf

    • 2 years ago
  5. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @FoolForMath That was the formula I mentioned I was able to find. However, it gives the incorrect value.

    • 2 years ago
  6. FoolForMath Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I think you are probably making mistake while implementing it. This looks correct to me.

    • 2 years ago
  7. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Their table is correct, but their formula is not. Try their formula for n=41, and x=40.

    • 2 years ago
  8. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    If I've typed it into wolfram correctly, that formula gives you -10, while the solution should be 35. http://www.wolframalpha.com/input/?i=1%2B2%2841%29-%282%2841%29-2%2840%29%2B1%29+%282%5E%281%2Bceiling%28log_2%28ceiling%2841%2F%282%2841%29-2%2840%29%2B1%29%29%29%29%29+-sgn%28ceiling%28ceiling%2841%2F2%29%2F2%29%29%29

    • 2 years ago
  9. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @joemath314159 is close. I believe his formula gives you the number of the child that gets the last present.

    • 2 years ago
  10. FoolForMath Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, as I said if you implement is right you will get 35.

    • 2 years ago
  11. FoolForMath Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Do you understand C?

    • 2 years ago
  12. FoolForMath Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    The recursive solution given there is right. I can't find my implementation so I had to fix a broken program available in internet and got 35 for n = 41 and x=40. And please don't say a published paper is wrong just like that :)

    • 2 years ago
  13. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Maybe I'm missing something critical then. But where did I type it incorrectly into Wolfram? My personal opinion is that they just made a small typo in the formula because I was able to make a very small modification that gave me the correct answer.

    • 2 years ago
  14. FoolForMath Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    When we are dealing with decimals (log) it's really hard to hold the precision even for the wolf. This is the C (recursive) solution, I was talking about: http://ideone.com/iJkuK

    • 2 years ago
  15. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Even using their formula by hand, I get an incorrect value for n=6.

    • 2 years ago
  16. FoolForMath Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Sorry, I haven't checked in the non-recursive version. But it's rather difficult to believe that the formula is incorrect :)

    • 2 years ago
  17. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Like I said, I believe it's a typo since it's easily changed so that I do always get the correct solution.

    • 2 years ago
  18. FoolForMath Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    The non-recursive version has little importance in computer science (programming) as it fails for sufficiently large \(n \).

    • 2 years ago
  19. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    For those just joining us, I know of two different closed form expressions that give me the correct solution. The first, is a modified form of the closed form expression in the link ffm provided above. http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf The second, is a formula more similar to what Joe had near the top. This is the formula I originally found on my own. Both formulas give the correct solution, although they look mildly different. I will accept either.

    • 2 years ago
  20. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Hint: Solve the problem for \(n=2^k\). Now go back to the general case. Reduce that case to a \(2^k\) case, and solve. In particular, what do you have to add in and then subtract?

    • 2 years ago
  21. Limitless Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Could you please compute for values from \(1\) to \(10\)?

    • 2 years ago
  22. Limitless Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I believe \(1\) is undefined, actually. Sorry.

    • 2 years ago
  23. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[n=5 \rightarrow 5\]\[n=6\rightarrow1\]\[n=7\rightarrow3\]\[n=8\rightarrow5\]\[n=9\rightarrow7\]\[n=10\rightarrow9\]I'll let you do 2-4 since they're fairly simple

    • 2 years ago
  24. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[n=2^4=16\rightarrow9\]\[n=20\rightarrow17\]

    • 2 years ago
  25. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @KingGeorge Solution??

    • 2 years ago
  26. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @Libniz

    • 2 years ago
  27. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    First up, we have the modified form of the equation linked to above. This is \[\Large 2n+1-(2n-2x+1)\left(2^{\left\lfloor \log_2 \left\lfloor \frac{n}{2n-2x+1}\right\rfloor\right\rfloor+1}-\text{sgn}\left(\left\lfloor \frac{\left\lceil\frac{n}{2}\right\rceil}{x}\right\rfloor\right)\right)\]With \(x=n-1\)

    • 2 years ago
  28. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Sorry, at the end it's just \[\Large -\text{sgn}\left(\left\lfloor \frac{\left\lceil\frac{n}{2}\right\rceil}{x}\right\rfloor\right)\]

    • 2 years ago
  29. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    The solution that I discovered on my own (both give the same values for all positive integers)\[\Large 2\left(n-2^{\left\lfloor\log_2(n)\right\rfloor}\right)+2^{\left\lfloor\log_2(n)\right\rfloor+1}+1\pmod{2^{\left\lfloor\log_2(n)\right\rfloor-1}\cdot3}\]

    • 2 years ago
  30. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Once again, the end is just \[\Large \pmod{2^{\left\lfloor\log_2(n)\right\rfloor-1}\cdot3}\]

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.