Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

KingGeorge

  • 3 years ago

[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.

  • This Question is Closed
  1. KingGeorge
    • 3 years ago
    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. KingGeorge
    • 3 years ago
    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.

  3. joemath314159
    • 3 years ago
    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 >.<

  4. FoolForMath
    • 3 years ago
    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

  5. KingGeorge
    • 3 years ago
    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.

  6. FoolForMath
    • 3 years ago
    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.

  7. KingGeorge
    • 3 years ago
    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.

  8. KingGeorge
    • 3 years ago
    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

  9. KingGeorge
    • 3 years ago
    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.

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

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

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

    Do you understand C?

  12. FoolForMath
    • 3 years ago
    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 :)

  13. KingGeorge
    • 3 years ago
    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.

  14. FoolForMath
    • 3 years ago
    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

  15. KingGeorge
    • 3 years ago
    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.

  16. FoolForMath
    • 3 years ago
    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 :)

  17. KingGeorge
    • 3 years ago
    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.

  18. FoolForMath
    • 3 years ago
    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 \).

  19. KingGeorge
    • 3 years ago
    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.

  20. KingGeorge
    • 3 years ago
    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?

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

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

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

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

  23. KingGeorge
    • 3 years ago
    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

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

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

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

    @KingGeorge Solution??

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

    @Libniz

  27. KingGeorge
    • 3 years ago
    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\)

  28. KingGeorge
    • 3 years ago
    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)\]

  29. KingGeorge
    • 3 years ago
    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}\]

  30. KingGeorge
    • 3 years ago
    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}\]

  31. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy