KingGeorge
  • KingGeorge
[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.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
KingGeorge
  • KingGeorge
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.
KingGeorge
  • KingGeorge
Also, if you want me to compute some test values for you, let me know what \(n\) to use.
anonymous
  • anonymous
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 >.<

Looking for something else?

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

More answers

anonymous
  • anonymous
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
KingGeorge
  • KingGeorge
@FoolForMath That was the formula I mentioned I was able to find. However, it gives the incorrect value.
anonymous
  • anonymous
I think you are probably making mistake while implementing it. This looks correct to me.
KingGeorge
  • KingGeorge
Their table is correct, but their formula is not. Try their formula for n=41, and x=40.
KingGeorge
  • KingGeorge
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
KingGeorge
  • KingGeorge
@joemath314159 is close. I believe his formula gives you the number of the child that gets the last present.
anonymous
  • anonymous
Well, as I said if you implement is right you will get 35.
anonymous
  • anonymous
Do you understand C?
anonymous
  • anonymous
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 :)
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
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
KingGeorge
  • KingGeorge
Even using their formula by hand, I get an incorrect value for n=6.
anonymous
  • anonymous
Sorry, I haven't checked in the non-recursive version. But it's rather difficult to believe that the formula is incorrect :)
KingGeorge
  • KingGeorge
Like I said, I believe it's a typo since it's easily changed so that I do always get the correct solution.
anonymous
  • anonymous
The non-recursive version has little importance in computer science (programming) as it fails for sufficiently large \(n \).
KingGeorge
  • KingGeorge
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.
KingGeorge
  • KingGeorge
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?
anonymous
  • anonymous
Could you please compute for values from \(1\) to \(10\)?
anonymous
  • anonymous
I believe \(1\) is undefined, actually. Sorry.
KingGeorge
  • KingGeorge
\[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
KingGeorge
  • KingGeorge
\[n=2^4=16\rightarrow9\]\[n=20\rightarrow17\]
anonymous
  • anonymous
@KingGeorge Solution??
anonymous
  • anonymous
@Libniz
KingGeorge
  • KingGeorge
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\)
KingGeorge
  • KingGeorge
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)\]
KingGeorge
  • KingGeorge
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}\]
KingGeorge
  • KingGeorge
Once again, the end is just \[\Large \pmod{2^{\left\lfloor\log_2(n)\right\rfloor-1}\cdot3}\]

Looking for something else?

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