Here comes Santa Claus
Posted by protozach on December 24, 2009
You wanted a hard problem? Hopefully this one makes sense. I’m uploading at 1:25 AM.
The Mathroom
For problems you can solve in one sitting.
-
Recent Comments
Geroger on Pendulous Folket on Here comes Santa Claus Faker on Pendulous Miguel on About MM on Here comes Santa Claus MM on Here comes Santa Claus MM on Astronomical Units Calvin on Math Anxiety Haruspex on Inscribed in Yo Mama Haruspex on Inscribed in Yo Mama
Subscribe
Brian said
oooh, wish I still had my probability book. I might be taking an unsupported leap here, but I’d go ahead and solve the (I think) equivalent question of what time we would expect him to reach his sleigh. For his first hour (720 steps at 5s intervals), the probability of going forward is only 1/2, so we expect santa to make zero net progress. For his second hour (3:00-3:59am) he moves forward twice as often as he moves backward, so to take 25 steps forward we would expect santa to have taken 37.5 total steps, so it’s 3:03:07.5 when we expect him to reach the sleigh. Since he only actually takes steps every 5s, the probability of him having reached the sleigh doesn’t exceed 50% until 3:03:10am
Walker said
I’m going to brute force it in google spreadsheet. Brb.
Ryon said
Trick question: he’s been mugged and passed out and wakes up around 9AM.
Walker said
6:45
Made a cell Q2 = 1
Made a cell Q3=P2/2 + R2/2, copied it all over the whole next 60/5 = 12 rows
Next 12 rows, have it be Q15=P14/3 + R14*2/3
Next, 1/4 and 3/4, etc
Have the col that’s 25 cols from the starting 1 be B20 = B19 + C16(whatever current multiplier is)
Leave left adder off for the next row; assume that santa doesn’t have a chance of leaving sleigh once in it.
THEN MASSIVE COPY PASTE CELLS!
http://spreadsheets.google.com/ccc?key=0AqdVH2GFQ888dFpPVFREUjZRUmxrMmh5aUNyOFViVHc&hl=en
(Least elegant solution ever amirite?)
Walker said
Wow moron, that’s for one step every 5 MINUTES not SECONDS!
nixonagnew said
“moron” was a little uncalled for. dude gave it his best shot.
nixonagnew said
rofl- now I’M the moron. just noticed both posts were by Walker. facepalm
David Stansby said
I’ve brute forced an experimental average number of steps in c++ http://pastebin.com/m5ec21baa . I’m getting an average of ~88.2 minutes in total. I don’t have a clue how to apply this answer to the question though…
David Stansby said
Turns out that was wrong. I’ve now got an average of ~2122 steps which equates to ~177 minutes, which is ~4:57am
Hailspork said
I got an average of 75 steps into 3:00. My reasoning being that during 2:00-2:59:55, the expected value per step is 0; during the 3:00 hour, the E(step) is .33333. So, 75 steps later, his E(steps) is 25m.
Cap'n Nobeard said
What about the probability of falling down and choking in one’s own vomit?
orthros said
Hmm, I came up with 3:07am.
From 2-3am, the expected value of forward motion is zero (1/2 forward / 1/2 backward).
Starting at 3am, the expected value of forward motion is 1 meter every 15 seconds (2/3 forward / 1/3 backward).
This equates to 4 meters every minute. At 3:07am (or 3:06.15, to be more precise) we have at least 50% probability of Santa hitting the sleigh.
Dahvid said
The expected in the first hour is zero movement.
In the second hour he will move forward twice and back once every 15 seconds, so he moves 1m every 15 seconds (4m per minute). So he arrives at the sleigh at 3:06:15. This is the time for 50% probability
Dahvid said
haha, then again – what orthros said
MM said
Not correct. It’s 2m every 15 seconds (2/3 forward, 1/3 backward), so he arrives at 3:03:7.5, but he doesn’t actually take a step until 3:03:10 so the time is 3:03:10.
requinix said
I’m going to be the odd one out and say it passes 50% before 3am. Like around 2:55:40.
Why?
Lemme ask you a question:
What if Santa only had to walk 2 meters? Would you say that in the entire one hour stretch he probably couldn’t do it?
Spoiler: after 8 steps it’s almost 51% likely that he did.
Platypus said
It looks like you allowed Santa to go farther than 25 meters away… 2:55:40 is almost exactly the average I got below (55.75 minutes) with no boundary at 0.
z said
Though you do have the right idea that it’s a lot smaller than most people expect, it’s not under 3 from my calculations at least.
At 3am, he only has ~35% chance to have reached 25, and closer to a 50% to reach 19. (assuming negative distance which you did for the example at least)
I do not know the answer to the question myself as it gets… ugly after 3, but if he continues at 50/50, it’ll take him almost 2 hours to average at 25.
Hailspork said
If you drop the distance to 1 meter, then at 2:00:05, it becomes 50%. However, that second meter makes a HUGE difference. You’re as likely to reach -2 meters as you are 2 meters, and while you have a 50% chance to reach 2 meters before -2 meters, you have no guarantee you will ever reach either one of them.
Though, if you want to test that theory, here’s how you do it. Make a matrix M, 103×103, representing 100 meters backwards, initial point, and 2 meters forward. On line X, put a value of .5 at X-1 and X+1, except lines 1 and 103; line 1 column 2 is 1, line 103 column 103 is 1. All other slots are 0. Now you have a Markhov Chain. Look at line 100: At step N+1, line X of M^N will give you the probability of being in a given meter.
Now, this unfortunately assumes that you can’t go further back than 100 meters, but it should give a good approximation.
Now, expand this to 25 meters, and try it out. The aproximation isn’t as good because of the whole -100 thing, but you can expand that as well.
Eric said
After 1 billion walks, I get that after 55 minutes and 42.6 seconds. The relative error (stdev/Nwalks) is .0001, or about a third of a second. So, somewhere right between 55:42 and 55:43.
Fun problem!
Eric said
Wow, nice proofreading, Eric. I AVERAGED 55 minutes and 42.6 seconds over 1 billion walks. This is with Santa’s first step being taken after 5 seconds (that is, he has travelled 0 meters at 0 seconds).
MM said
No.
J said
I suck at math, Zach, so I probably won’t be able to do any of these. However they are quite fun to ponder. Thanks for another great site!
Social Scientist said
The expected distance covered over the first hour is not zero. Assuming Santa’s girlfriend has closed the door, his distance from the sleigh cannot exceed 25 metres. As the possibility of getting farther away does not exist the expected distance will closer than 25 meters. There is a 50% chance that at 3am he is still at the door, and a 50% chance he has made some headway towards the sleigh. I will leave the math grinding to someone else.
David Stansby said
If he can’t go backwards, there’s a 50% chance after 5 minutes that he’s at the door and a 50% chance that he’s move too
David Stansby said
And just out of interest, if he can’t go back then it should take him on average ~2.07 hours to get there.
Julius said
What I want to know is what the heck is the girlfriend doing watching Santa pace back and forth to the sleigh? 25m is a long distance! And if she’s at the window observing for an hour, or two, that’s pretty weird!
Stephen said
In Santa’s girlfriend’s defence I think we’ve all sat and watched the drunk do funny things for longer than is charitable.
Platypus said
Its not specified if he tries to go farther away than 25 meters. He could stay at zero, or he could bounce off, which makes the first hour a Markovian random walk with a reflective boundary. Think of a diffusing gas molecule — because of the boundary, the odds of Santa being exactly at 0 when it ticks 3:00 are extremely small.
I wrote a small perl script to simulate this; on average Santa took 41.216 minutes (494.6 steps) to reach his sleigh, with a minimum of 3.083 minutes (37 steps) and a maximum of 81 minutes (972 steps), out of 100,000 trials.
Michael Leuchtenburg said
What’s the standard deviation you find in that 100k trials?
Given that you’re seeing maximum deviations of -459.6 and 477.4, I’m guessing σ ≈ 100, since with 100k trials we’d expect the most extreme values to be deviating by about σ * 4.27.
Platypus said
I wasn’t keeping the results of each trial (just average / min / max). However I don’t know where you got your 4.27 ratio from, but its probably based on assumptions that don’t apply here since we have boundaries on our outcomes (the minimum possible result is 25 steps — around a 1 in 34,000,000 chance btw — and once we hit 3:00 santa’s movement becomes directional.) Also standard deviation shouldn’t be a function of sample size, except that the actual observed value for s.d. will converges to the true answer as the sample size gets large.
I rewrote the code to calculate standard deviation, and I get σ ≈ 19.79 from 100,000 trials.
Michael Leuchtenburg said
Hm, I was drastically off in my standard deviation estimation. The actual value with your code is around 19.8 minutes, or 237.6 steps.
Code here: http://codepad.org/g6bm9xfz
Eric said
Here’s my c++ code for doing a billion walks in a couple minutes:
http://codepad.org/StkOyBu4
It’s using Ziff and Newman’s prng, but I didn’t include that because I figured you didn’t care how it wirks. I also get 3342.6 seconds, plus or minus .3 seconds. That’s 55 minutes and between 42.3 seconds and 42.9 seconds.
Platypus said
Also, if we allow Santa to stumble back into the house (so he can go farther than 25 meters away from his sleigh) then the average time goes up to 55.75 minutes (669 steps) with a minimum of 35 steps and a maximum of 1,217 steps.
Michael Leuchtenburg said
I think you guys are missing some important factors here.
1) At the end of the first hour, Santa is probably not at x=0. Why? Because he can never be at x=-1, that is, he can never go back into his girlfriend’s house.
2) You probably can’t solve this numerically unless you’re very careful. Why? The precision required is very high.
Michael Leuchtenburg said
That said, here’s a quick and dirty probability calculating numerical solution. This could bo done better with some higher precision numbers; I’ve cheated by rescaling the probabilities so that they sum to 1, here.
http://codepad.org/VNnBG5bd
The answer I get is 2:39:20. Pretty darn close to the other answers we’re getting.
Anyone have an exact solution?
Michael Leuchtenburg said
Got the same results using 1000 digit decimals.Decimal types, so I’m pretty confident in the 2:39:20 number now. The probabilities sum to 1 without rescaling, done that way.
http://codepad.org/kbn8epPS
Platypus said
Thanks for the codepad link, I wasn’t aware of that site. Here’s the perl code I used.
http://codepad.org/sn3r6pmL
Andrej said
Michael brings up good points. But the restriction that santa can’t go below x=0 makes the problem much more difficult to solve analytically, I would say. On the other hand discretization is enemy of mathematics so I can’t see a simple way of doing this problem analytically. The simulation is of course still easy, but I don’t think the required precision is THAT big of a problem.
Python code, taking into consideration the fact that Santa can’t go less than x=0:
s,t=0,0
while s<25:
s= max(0,s-1) if uniform(0,1)=0 restriction gives 55.79 minutes
But more interestingly, here are the histograms of the number of minutes it takes:
http://img121.imageshack.us/img121/3766/santas.jpg
Andrej said
Ahhh my code was screwed up in the post. Here is the full code that even generates the histograms
http://codepad.org/vsQE4exH
Sean said
let P(x) be the probability that Santa will reach the sleigh after x steps (or equivalently after x*5 seconds)
Trivially for x= .5
Naively written code will take forever to solve, however we can easily export this to excel and solve. In that case the first time P(x) is >= .5 is at x=473 when Santa cannot step backwards (that corresponds to 2:39:25. That may be off 5 seconds either way due to rounding errors, but the gist still remains.
Now, if Santa can step past -1 we have a different story. The number then comes out to x=739 (again give or take 1 for rounding) which corresponds to 3:01:35
Sean said
Sorry, it stripped the fun stuff from the post. not really sure why…. here’s what it was
[pre]
P(x) = Pa(x,0) where Pa(x,y) is the probability of reaching the sled with x steps starting from position y
Pa(x,y) =
if y=25 then 1
if x+y<25 then 0
if y=0 then Pa(x-1,1)
else
(1/(2+((int)x/720)))*Pa(x-1,max(0,y-1)) + (1-(1/(2+((int)x/720))))*Pa(x-1,y+1)
[/pre]
Platypus said
Your 2:39:25 is the same as Michael Leuchtenburg got above… I keep getting an answer around 2 minutes higher. I wonder if I have an off-by-one in the while loop…
if I change the test to while $position < 24 (instead of 25) then I get 39.2 minutes.
just a guy said
I wrote a small python script to simulate this stuff.
If there is a reflective boundary, i reach 50% probability after 113 minutes (3:53)
If there is no reflective boundary, i reach 50% probability after 128 minutes (4:08)
I also got an exact solution to the unbounded case using somewhat of a “brute force” solution in Mathematica:
Consider P[k,t] the probability he walked k of the steps backwards, after t minutes.
If he walked t-k steps forward and k steps backwards, the total distance from the sleigh is t-2k
So the probability Santa reached the sleigh after t minutes is Sum[P[k,t]] over every non-negative k so that t-2k>=25. In other words for k between 0 and (t-25)/2.
Now we need to define P[k,t] and that were the “brute force” comes into play:
For tt>=60: we iterate over every possibility of geting mt>=120: we iterate over every possibility of geting m<k errors in the first two hours and the rest in the third hour
Now we test the sums of P[k,t] over every appropriate k for a few values of t, and find that the probability for t=127 is 0.4838, but the probability for t=128 is 0.53855
The problem with this approach is that we supposedly allow Santa to go back after he already reached the sleigh, and don't count cases where he went back towards the house. But the probability of this happening is very very small, certainly under 1%
just a guy said
small edit:
instead of “distance from the sleigh is t-2k” in the third paragraph it should be “distance from the house is t-2k”
just a guy said
And of course i used 1 minutes step instead of 5 seconds.
Everything i wrote is worth nothing i guess, except maybe the Mathematica approach
Flavin said
Why does everyone think he can’t go into negative distance? The problem didn’t specify the sleigh was 25 m away in a direction normal to the front door. Maybe it’s 25 m down the sidewalk to the right, and the sidewalk extends infinitely in both directions.
I’ll solve on the assumption that Santa could go negative.
The probability of getting to any spot after N steps is
In case the LaTeX doesn’t work, this says
(p+)^(n+)*(p-)^(n-)* ( N choose n+ )
That is, the probability of going right to the number of steps right times probability of left to the steps left times the binomial coefficient that gives the number of ways you could have gotten those numbers of steps, N choose n+ (or n-).
Since we only care about combinations that give us 25 steps right, I’ll note
This allows us to solve for n+ and n-. So in terms of just N, the probability of getting to the sleigh in N (odd) steps is
Now it’s a simple matter of summing over odd N from 25 up to some number S, where S will be the number of steps we want once the sum is greater than 50%. (Note that this overcounts slightly, as it includes cases where Santa overshoots the sleigh then comes back. We could correct for this, but I think the correction would be pretty minor and the work tedious. So f it.)
Mathematica code:
Sum[(1/2)^N Binomial[N, (N + 25)/2], {N, 25, S, 2}] /. {S -> 211} // N
0.510917
Therefore after 211 steps (= 17.58 minutes) Santa has more than likely gotten to the sleigh.
WiseBinky79 said
there is a 50% chance he never progresses for one hour. After one hour, at 50% probability, he progresses with 50% probability at 2 meters every 15 seconds. it will then take him, at this probability, 187.5 seconds after the hour to reach. Therefore, he reaches the sleigh slightly after 3:03 AM with 50% probability.
nickmagus said
Ok so I ran a simulation on this with increasing precision up to 1 million trials (starting at 100 and adding two 0s to get good starting points so it wouldn’t take forever) and here are the times I get:
If santa’s distance traveled cant go below 0: 2:41:05
if it can: 3:05:05
WiseBinky79 said
I’m assuming he can go negative distance in my answer. Also, I should be clear, that I’m using the 50% probability as a constant, not as on occurrence.
WiseBinky79 said
Do you know if there is an answer to this, or if Zach will post the answer sometime?
pete s. said
My interpretation is that a) once he reaches the sled he stays there b) there is nothing preventing him from moving further back than the starting point. This is a simple enough setup that you can easily calculate exactly what the probability is of Santa being at any particular spot at any time. It’s just a discrete Markov chain, and you only have to track finitely many states, since there are only so many states he can reach in the relevant time interval.
Matlab code:
N = 1000;
A2 = spdiags(ones(N,1)*[1,0,1]/2,-1:1,N,N); A2(1,1:2)=[1,0]; A2(N,N-1:N)=[0,1];
A3 = spdiags(ones(N,1)*[1,0,2]/3,-1:1,N,N); A3(1,1:2)=[1,0]; A3(N,N-1:N)=[0,1];
p = zeros(1,N); p(N-25) = 1;
for t=5:5:60*60*2, if t = .5, break, end, end
Conclusion:
At 3:05:00 the probability of having reached the sled is .49447
At 3:05:05 the probability of having reached the sled is .50192
pete s. said
Bah, less than and greater than symbols messed up that last line of code. It should be:
for t=5:5:60*60*2
if t (less than or equal to) 60*60, p=p*A2; else, p = p*A3; end
t,p(N)
if p(N) (greater than or equal to) .5, break, end
end
777 said
2:02:05?
I suck at math, as you can see.
Jason said
While being at x=0 after one hour is the most likely possibility (assuming no boundary), the odds of him actually being there are only (720c360)/2^720, or 0.0297.
Kevin said
After 1 step, there is a 50% chance he will have walked one metre. Thusly, after 2 steps, there is a (50%*50%) or 25% chance that he will have walked two metres. And then after 3 steps, a (50%*50%*50%) or 12.5% chance that he proceeded forward three times in a row. Continuing that pattern ad infinitum, I concluded that the earliest he could possibly reach the sleigh is after 25 steps, or 2 minutes, 5 seconds. But the odds of moving forward 24 times consecutively is only (100*(2^25)%. In other words, almost impossible.
On the 26th step, I assumed he would stop walking if he was already at the sleigh. I figured he had a (100*(2^25)% chance of being at 1 metre away following his 25th step, so that gives a new chance of (100*(2^26)% chance of arriving, plus the old chance. But, following that logic, he never reaches the sleigh.
This math hurts my head… ?_?
LN said
Kevin, sure he does. Eventually, the accumulated probability rises above 50%. It’s an infinite sum. Also, keep in mind that every hour the probability that he moves forward increases by a significant amount. Saying “never” means that even when he hits 10 AM and has a 90% chance of moving forward, he still can’t ever have a 50% chance of reaching the sleigh.
Kevin said
The reason I jumped to the conclusion of “never” is the sum of the values kept growing and eventually the probability got so small that excel rounded it to 0… I’ve since tried again with Java, to see if I get a better result. And, upon further calculation, I’m even more confused than before.
After one hour of walking, the sum adds the value (100 /(2^720))% and the total is then 5.9604644775390625E-6%. But, after that, Santa has a 2/3 chance of moving forward, rather than a 1/2 chance as before. So, do I add (100 * (0.6666^1)% to the value? That makes the answer then 3:00:05 AM. And no one else has come up with that answer, so I’m fairly certain it’s wrong.
I just get more and more confused each time I try this.
Flavin said
Think about the situation after he’s taken 27 steps. The only way he could be on spot 25 is if he has taken 26 positive steps and 1 negative step. The probability of that combination is, as you’ve said, 1/2^27. However, you have to multiply those probabilities by a binomial coefficient, 27 choose 1, which is the number of different combinations of 26 positive and 1 negative he could have. In other words, the negative step could be the first one, the second one, the third one, …, and you have to multiply by that number. So for 27 steps, you would multiply (1/2^27)*27 to get the probability. This is still not very big, but it grows quickly as the number of steps grows.
Kevin said
So then that means that after 720 steps, it would be (0.5^720)*720. I follow the math so far, but what happens on the 721st step, when he has a 2/3 probability of moving forward?
Matt said
Well, experimental probabilities seem to be backing up the “just after 3″ answer.
My trials:
public class drunkSanta{
public static void main(String[] args){
int hours = 2;
int minutes = 0;
int seconds = 0;
boolean step = false;
double seed = 0;
double limit = 0.5;
int distance = 25;
while(distance > 0){
seed = Math.random();
if(seed > limit) step = true;
else step = false;
if(step) distance–;
else distance++;
seconds = seconds + 5;
if(seconds == 60){
seconds = 0;
minutes++;
}
if(minutes == 60){
minutes = 0;
hours++;
limit = 1.0/hours;
}
}
if(minutes < 10){
if(seconds < 10) System.out.println("Santa made it to his sleigh at " + hours + ":0" + minutes + ":0" + seconds + " AM.");
else System.out.println("Santa made it to his sleigh at " + hours + ":0" + minutes + ":" + seconds + " AM.");
}
else{
if(seconds < 10) System.out.println("Santa made it to his sleigh at " + hours + ":" + minutes + ":0" + seconds + " AM.");
else System.out.println("Santa made it to his sleigh at " + hours + ":" + minutes + ":" + seconds + " AM.");
}
}
}
mac404 said
You shouldn’t think of this problem strictly in terms of expected values. If, for instance, he had to walk far enough away that it will take him over two hours, this method no longer works (as the probability of being n steps to the left of the expected is different than being n steps to the right of the expected at the end of two hours. The distribution is no longer symmetric about the mean). If we wanted to use a probability other than 50%, this method also fails.
One can theoretically create a finite transition matrix with an absorbing state at 25 and a lower bound at the farthest possible negative distance for each individual step, find the probability distribution of being at each individual spot), and then iterate through the process until the probability of any desired outcome is reached (but that would be ridiculous given the number of steps involved and the very small probabilities that show up will create rounding issues). The better method would be to determine
mac404 said
And I accidentally hit send too early. Thinking about this more, I have two issues with the current solutions:
1. You should first think harder about why the probability of Santa walking 25 meters forward is less than half through the first hour. You all seem to argue that because he is expected to be in the same spot as he started if he walks according to the rules unbounded, this is true (and I agree). But 25 is an absorbing state (probability of staying at 25 once reach 25 is 1), which makes this statement much less trivial. There is a non-zero probability of being at the sleigh after an hour. The expected value of the first hour of this process is very likely NOT zero.
2. At least as importantly, the right side being unbounded is abused into the second hour. The probability of being -24 steps from where you started will likely be larger than the probability of being 24 steps from where you started after an hour (given that any possible outcome that reaches 25 no longer has the chance to go back below 25).
The problem is NOT symmetric, even during the first hour.
whatisfgh said
The easy way to see that it can’t be 50% in the first hour (assuming he can go backwards) is that the sum of the negative distances probabilities is .5 (sum 0 to k-1/x) (k chose i) = 2^(k-1)
It becomes non symmetric at 2:02:10 (if that matters)
whatisfgh said
oops ignore that easy part.. I forgot the bump at 25 moves back at something like 1 meter per step after step 25.
Hailspork said
I’m going to repeat this comment here, since it’s basically the solution. It was a reply to “try it with only 2 meters”.
If you drop the distance to 1 meter, then at 2:00:05, it becomes 50%. However, that second meter makes a HUGE difference. You’re as likely to reach -2 meters as you are 2 meters, and while you have a 50% chance to reach 2 meters before -2 meters, you have no guarantee you will ever reach either one of them.
Though, if you want to test that theory, here’s how you do it. Make a matrix M, 103×103, representing 100 meters backwards, initial point, and 2 meters forward. On line X, put a value of .5 at X-1 and X+1, except lines 1 and 103; line 1 column 2 is 1, line 103 column 103 is 1. All other slots are 0. Now you have a Markhov Chain. Look at line 100: At step N+1 (for N 720, replace the left side .5′s with 1/hour and the right sides with (hour-1)/hour, and repeat for the next 720 iterations.
Now, this unfortunately assumes that you can’t go further back than 100 meters, but it should give a good approximation.
Now, expand this to 25 meters, and try it out. The aproximation isn’t as good because of the whole -100 thing, but you can expand that as well.
whatisfgh said
After matching this with some brute force calculations, it looks like for an exact answer this is the way to go, though you need something like an 1800X1800 matrix with the lower 900×900 as the markhov matrix to avoid loss of data. of course this means you need something like an 1800×1800 matrix with non 0 entries consisting of 216 digits and or accurate to the… lots… of decimal places
If I was at home I’d just do like everyone else and write a program that models the problem and run lots of trials.
If you actually do brute calculations you notice that it’s just millions of recursions… that are completely contained in the multiplication of the markhov matrices so why the hell did I spend 6 hours doing them last night… wait.. or is that just me?
whatisfgh said
Oh and if you can get numbers that big or accurate you don’t need a matix you just need 1 X+ 25 sized array where X is something like 100 + whatever the models everyone has done already has shown (to be safe)
the it’s just a rough algorithm like
Array as index’s (-900 to 25)
array(i) = 1 if x = 0, 0 else
steps = 0
for i = 2 to 3
exit if array(25) >.5
steps++
temparray has indexes (-900 to 25) all entries 0
array(25) = (1/i)*array(24)
for j = -899 to 24
temparray(j) = (1/i)*array(j-1) +(1-1/i)array(j+1)
next
for j = 899 to 24
array(j) = temparray(j)
next
next
Now hopefully I didn’t screw that up with my festivus whiskey
whatisfgh said
fusk no I screwed it up, for k = 0 to #steps per hour somewhere in there. In the place that makes it work.
whatisfgh said
For the bitch won’t let me back in the door variant, it’s just a 0 to 25 array
same algorithm basically save that there’s a
temparray 0 = (1-1/i)*array(1)
and j only goes from 1 to 24
these are literally just making your computer brute force the probabilities
Thomas said
After 492 steps, the possibility that he reached 25 meters is 50,0150340636 %
(solved with PHP script
1);
$forwards = 1/2; //init
$backwards = 1/2;
$probability_total = 0.0;
for ($step=0;$step $probability) {
if ($meter <25) {
$metermore = $meter + 1;
$meterless = $meter – 1;
if ($meterless < 0) { //Er kann nicht = 0.5) {
break;
}
} else {
$steps[$step+1][$metermore] += $probability * $forwards;
}
$steps[$step+1][$meterless] += $probability * $backwards;
}
}
if($probability_total >= 0.5) {
break;
}
}
echo ‘
‘;
echo $probability_total;
?>
i_failed_calc_2 said
I get just after three using the script:
public class drunkSanta{
public static void main(String[] args){
int solution = 0
int what they said = just after three
if(me = tired) solution = what they said
else solution = after santa has died of hypothermia
}
}
LN said
There’s a slight problem with the latest assumptions. Both sides are bounded.
Why? Santa left his girlfriend’s house. How many girlfriends leave the door open in the middle of a winter night to allow their boyfriends to stumble back into their homes after they kick them out at 2 AM?
whatisfgh said
This was already addressed. How many people park 25 m in front of the door? Anyone using unbounded negatives are assuming that santa is parked 25 m down the street. (though finding both answer is “like” bonus points.
LN said
Fair point. I didn’t think of that.
Thomas said
If you count boundaries (Santa can’t go back in his girlfriend’s house) -> 492 steps (2:41 AM)
If you think that Santa can go back in his girlfriend’s house and it’s relatively huge (779 meters) -> 781 steps (3:05 AM)
I tried to solve the problem with a PHP snippet, basically creating a probability tree (using the La Plasc-formula)
Is there a solution published by the autors to compare with?
PHP-Code:
1); $forwards = 1/2; //init $backwards = 1/2; $probability_total = 0.0; for ($step=0;$step $probability) { if ($meter <25) { $metermore = $meter + 1; $meterless = $meter - 1; //if ($meterless activate // $meterless = 0; //} if ($metermore == 25) { $probability_total += $probability * $forwards; if($probability_total >= 0.5) { break; } } else { $steps[$step+1][$metermore] += $probability * $forwards; } $steps[$step+1][$meterless] += $probability * $backwards; } } if($probability_total >= 0.5) { break; } } print_r($steps); echo $probability_total; ?>The Red Monkey of Stool said
Here’s to simulate the problem exactly:
#include
#include
#include
#define TIME_START (2*60)
#define SIMS 10e5
int step(int hour)
{
if(!(rand() % hour)) return -1;
return 1;
}
int hour(int time) {
return time / 60;
}
int minute(int time) {
return time % 60;
}
int simulate()
{
int t = TIME_START;
int dist = 0;
while(dist < 25) {
dist += step(hour(t));
t += 5;
}
printf("Sata is at the sleigh at %d:%d\n", hour(t), minute(t));
return t;
}
int main(void)
{
int i;
long int t_avg;
srand(time(0));
for(i=0, t_avg=0; i<SIMS; i++) {
t_avg += simulate();
}
t_avg /= SIMS;
printf("Average: %d:%d\n", hour(t_avg), minute(t_avg));
return 0;
}
The Red Monkey of Stool said
Doh! Code formatting….
#include
#include
#include
#define TIME_START (2*60)
#define SIMS 10e5
int step(int hour)
{
if(!(rand() % hour)) return -1;
return 1;
}
int hour(int time) {
return time / 60;
}
int minute(int time) {
return time % 60;
}
int simulate()
{
int t = TIME_START;
int dist = 0;
while(dist < 25) {
dist += step(hour(t));
t += 5;
}
printf("Sata is at the sleigh at %d:%d\n", hour(t), minute(t));
return t;
}
int main(void)
{
int i;
long int t_avg;
srand(time(0));
for(i=0, t_avg=0; i<SIMS; i++) {
t_avg += simulate();
}
t_avg /= SIMS;
printf("Average: %d:%d\n", hour(t_avg), minute(t_avg));
return 0;
}
samuelmay said
I saw this as a Markov chain with a finite state space with 26 states (the front door, the sleigh, and the 24 meters in between them).
The probability of Santa taking a step forward from the front door is 1, so P_1,2 is 1. The probability of Santa staying in his sleigh once he gets there is 1 (he sleeps it off in the back) so P_26,26 is 1. For the other states, the probability of a step backwards P_n,n-1 is 1/x, and a step forward is P_n,n+1 is 1-1/x. All other transitions have probability 0.
At the start, Santa is at the front door, so the state vector is S = (1,0,0,0…0). Simply compute S = S*P until S_26 > 0.5, updating the transition matrix every hour.
The following matlab program gave me 2:39 and 25 seconds.
% solution to the Mathroom problem 'Here Comes Santa'
%
% random walk Markov chain. the states are
%
% door | 1m | 2m | .... | 24m | sleigh |
% state S1 S2 S3 .... S25 S26
% probability of transition from S1 to S2 is 1.
% probability of transition from S26 to any other state is 0.
% otherwise,
% probability of transition from Sn to Sn-1 (backwards step) is 1/x
% probability of transition from Sn to Sn+1 (forwards step) is 1-1/x
% any other transition has probability zero (santa doesn't jump).
function P = transition_matrix(hour)
P = zeros(26,26);
P(1,2) = 1; % he pushes off from the front door
% forward steps
for i = 2:25
P(i,i+1) = 1-(1/hour);
endfor
% backwards steps
for i = 2:25
P(i,i-1) = 1/hour;
endfor
P(26,26) = 1; % santa sleeps it off in the back
endfunction
P = transition_matrix(2); % transition matrix
S = zeros(1,26); % state vector
S(1) = 1; % santa starts at the door
t = 0;
while ( S(26) < 0.5 )
S = S * P;
t = t + 5;
if (t == 3600)
P = transition_matrix(3);
elseif (t == 2*3600)
P = transition_matrix(4);
endif
endwhile
hour = 2+floor(t/3600);
minute = floor(rem(t,3600)/60);
second = rem(t,60);
printf("Santa reaches his sleigh at %i:%i and %i seconds.",hour,minute,second);
Mauro said
Hm, I got 782 steps, or 3:05:10, by assuming that his first actual step is at 2:00:05. What I did:
I assumed that Santa can go infinitely far behind the house but will actually stop at the sleigh. p(x,n) = (h-1/h)*p(x-1,n-1) + (1/h)*p(x+1,n-1), except that for x = 24, only the first term is there (since Santa will never leave the sleigh once he gets there) and for x = 25, it’s only the first term plus p(25,n-1) (since Santa actually stays there). Running this in Matlab gives step 782 as the first when p(25,n) exceeds .5. I did it by setting up a grid down to -1075, since 2^-1074 is the smallest power of 2 allowed by Matlab (though this wasn’t strictly necessary, since h goes up to 3 before any probability can leak there, but I’m lazy). The difference between the probability at steps 781 and 782 is .007, so there’s no way that a machine epsilon of 2^-1074 could have affected anything at 782 steps.
epsilon said
That’s not what a machine epsilon is.
Machine epsilon is the smallest number such that 1 + eps != 1 which is about 2^-16 in double precision.
Eric said
I’ll agglomerate my contributions here:
code- http://codepad.org/StkOyBu4 – average 55 minutes and 42.6 seconds to get to the sleight from 1bn trials assuming no boundaries, 41 minutes and 12 seconds from 1bn trials assuming Santa can’t backtrack into the girlfriend’s place.
video- http://www.youtube.com/watch?v=qHr7FTqPYDk – “Santa Claus is coming to town” a unexpected gift from my Mother-in-law that is appropriate for this math problem, and probably nowhere else.
Thanks for the post-christmas fun!
LN said
You know, if there’s no lower bound, this is a simple system of binary coefficients. There’s no need for all this fancy stuff. And if there is a lower bound at 0, then it’s the binary coefficients are simply redistributed in an easily-identifiable way.
I’m working on it, but I don’t have the programming knowledge that most of you evidently do.
Lizzy said
I want to know how this problem would be affected if going backwards at 0 means he goes back in and sleeps with his girlfriend for x more minutes and then leaves and tries to get to his sleigh again.
Folket said
At 3:05:05 it will be 50% chance that Santa has reached the sleigh.
Two must common mistakes here is
1, assume net move is 0 during the first hour. This is not true after the first hour Santa has 35% to have reached the sleigh 54.3% is closer to the sleigh while 44.2% is further away. This is because if Santa reaches the sleigh he will not go back. By assuming zero movement you include the possibility that Santa reach the sleigh and then walked back.
2, people who have been running computer simulations have used the average time to estimate when the chance is 50%. This would work if the chance was symmetric in time. As it is now the chance grows very fast after the first hour which makes the average time shorter. For example the greatest chance to arrive on a single step after one hour is 0.80% at step 805, while during the first hour the greatest chance was 0.15% at step 206 and 208.