## Easy DDR-related puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Easy DDR-related puzzle

If you average 1 mistake per song, what is the probability that you will complete the song without making any mistakes?

(Assume the song is very long, and mistakes are equally likely on every step.)

Spoiler:
Yes, this is an easy question. It does, however, become much more difficult when you are trying to work out the answer and complete a song (7-feet, I can't get full combos on anything harder) without making any mistakes at the same time.

For those who don't know, DDR works as follows: during a song, there are a number of steps you must hit with correct timing. If you make a mistake, it breaks your combo, and I wanted a full-song combo (every step with great or perfect timing).

Spoiler your solution - there's no need to create a separate thread.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

++$_ Mo' Money Posts: 2370 Joined: Thu Nov 01, 2007 4:06 am UTC ### Re: Easy DDR-related puzzle Spoiler: Yes, indeed, this is an easy question. Start with the case where there are n > 1 steps in every song. If you make an average of one mistake per song, that means that the probability of a mistake on any given step is 1/n. Therefore, the probability of not making a mistake on any given step is [imath]1 - {1 \over n}[/imath]. Therefore, the probability of not making a mistake in the whole song is [imath]\left(1 - {1 \over n}\right)^n[/imath]. As [imath]n \to \infty[/imath], therefore, the probability approaches 1/e. In general, if you make an average of k mistakes per song, the probability of getting a full-song combo is [imath]e^{-k}[/imath]. Question: Suppose you want to get really long combos, even if you don't finish the song perfectly. If you make an average of one mistake per song, what's the expected length of your longest combo? I don't actually know the answer. skeptical scientist closed-minded spiritualist Posts: 6142 Joined: Tue Nov 28, 2006 6:09 am UTC Location: San Francisco ### Re: Easy DDR-related puzzle As n tends to infinity, the length of the longest combo also clearly tends to infinity. If you are interested in the length of the longest combo as a ratio of the total length, it would be 3/4 if you made exactly one mistake in every song, but I'm not sure what it would be if you made 1 mistake in n steps, on average, where n is the length of the song. I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side. "With math, all things are possible." —Rebecca Watson Patashu Answerful Bignitude Posts: 378 Joined: Mon Mar 12, 2007 8:54 am UTC Contact: ### Re: Easy DDR-related puzzle Solving DDR logic puzzles while playing DDR? I dunno, I think I still prefer people juggling while playing DDR (not that I can do it) (juggle that is) skeptical scientist closed-minded spiritualist Posts: 6142 Joined: Tue Nov 28, 2006 6:09 am UTC Location: San Francisco ### Re: Easy DDR-related puzzle Wow, that's pretty impressive. When I just try to do the hand-motions to YMCA my footwork goes all to hell. I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side. "With math, all things are possible." —Rebecca Watson Cauchy Posts: 602 Joined: Wed Mar 28, 2007 1:43 pm UTC ### Re: Easy DDR-related puzzle The expected length of your combo before making your first mistake is $\frac{1}{n}0 + \frac{n-1}{n}\frac{1}{n}1 + \left(\frac{n-1}{n}\right)^2\frac{1}{n}2 + \ldots + \left(\frac{n-1}{n}\right)^{n-1}\frac{1}{n}\left(n-1\right) + \left(\frac{n-1}{n}\right)^n n =$$\left(\frac{1}{n}0 + \frac{n-1}{n}\frac{1}{n}1 + \left(\frac{n-1}{n}\right)^2\frac{1}{n}2 + \ldots + \left(\frac{n-1}{n}\right)^n\frac{1}{n}n + \left(\frac{n-1}{n}\right)^{n+1}\frac{1}{n}\left(n+1\right) + \ldots\right) - \left(\left(\frac{n-1}{n}\right)^{n+1}\frac{1}{n}1 + \left(\frac{n-1}{n}\right)^{n+2}\frac{1}{n}2 + \ldots\right) =$$\left(n-1\right) - \left(\frac{n-1}{n}\right)^n\left(n-1\right) \approx n\left(1 - \frac{1}{e}\right)$for large n. This is about .63n, so that gives a lower bound on the expected length of your max combo. (∫|p|2)(∫|q|2) ≥ (∫|pq|)2 Thanks, skeptical scientist, for knowing symbols and giving them to me. Patashu Answerful Bignitude Posts: 378 Joined: Mon Mar 12, 2007 8:54 am UTC Contact: ### Re: Easy DDR-related puzzle skeptical scientist wrote:Wow, that's pretty impressive. When I just try to do the hand-motions to YMCA my footwork goes all to hell. Like I said, I don't expect to ever be able to do this but http://www.youtube.com/watch?v=06m-S8U_XUA Godskalken Posts: 159 Joined: Wed May 14, 2008 3:29 pm UTC ### Re: Easy DDR-related puzzle Did noone else wonder what this puzzle had to do with der Deutschen Demokratischen Republik? I must be getting old. Blatm Posts: 638 Joined: Mon Jun 04, 2007 1:43 am UTC ### Re: Easy DDR-related puzzle Patashu wrote: skeptical scientist wrote:Wow, that's pretty impressive. When I just try to do the hand-motions to YMCA my footwork goes all to hell. Like I said, I don't expect to ever be able to do this but http://www.youtube.com/watch?v=06m-S8U_XUA I can only imagine how many tokens he's spent to achieve that. zed0 Posts: 179 Joined: Sun Dec 17, 2006 11:00 pm UTC ### Re: Easy DDR-related puzzle Blatm wrote:I can only imagine how many tokens he's spent to achieve that. Well I can only just pass So Deep (the song he's playing) without juggling and I probably put about £10 (~$20) a week into DDR machines, and about half of that is our student union machine which is half the normal price.

Patashu
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

### Re: Easy DDR-related puzzle

I'm weird. I can pass max 300 on a ddr cabinet but not so deep heavy. About half way through the patterns just blur together for me, it's all too similar but varying just enough to make it hard to keep with.

Curse youuuu so deep!

Xalerwons
Posts: 13
Joined: Mon Apr 07, 2008 7:19 pm UTC

### Re: Easy DDR-related puzzle

skeptical scientist wrote:If you average 1 mistake per song, what is the probability that you will complete the song without making any mistakes?

(Assume the song is very long, and mistakes are equally likely on every step.)

From the information given, the probability of completing a song without making any mistakes is indeterminable.

meat.paste
Posts: 404
Joined: Fri Apr 25, 2008 3:08 pm UTC

### Re: Easy DDR-related puzzle

This should follow the Poisson distribution, which means that the answer is...

Spoiler:
nke-n/k!

where k is the number of mistakes (0 here) and n is the expected frequency (1 mistake per song)

This makes the answer for exactly 0 mistakes 1/e. This is also the answer for exactly 1 mistake. The probability that you will make more than 1 mistake is 1 – (2/e), which is ~26.4%

When the dance revolution comes, the first thing we do is shoot all the lawyers...
Huh? What?

Xalerwons
Posts: 13
Joined: Mon Apr 07, 2008 7:19 pm UTC

### Re: Easy DDR-related puzzle

meat.paste wrote:This should follow the Poisson distribution, which means that the answer is...

Spoiler:
nke-n/k!

where k is the number of mistakes (0 here) and n is the expected frequency (1 mistake per song)

This makes the answer for exactly 0 mistakes 1/e. This is also the answer for exactly 1 mistake. The probability that you will make more than 1 mistake is 1 – (2/e), which is ~26.4%

When the dance revolution comes, the first thing we do is shoot all the lawyers...

I'm not too mathematically inclined, but I fail to see how that works. You don't know the frequency of his mistakes.

meat.paste
Posts: 404
Joined: Fri Apr 25, 2008 3:08 pm UTC

### Re: Easy DDR-related puzzle

The OP said you average 1 mistake per song, so I used that as the expected frequency. The desired answer is the probability of making no mistakes. That is enough information to solve the problem.
Huh? What?