Easy DDR-related puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Easy DDR-related puzzle

Postby skeptical scientist » Mon Jun 02, 2008 10:42 pm UTC

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

Postby ++$_ » Mon Jun 02, 2008 11:04 pm UTC

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.

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

Re: Easy DDR-related puzzle

Postby skeptical scientist » Mon Jun 02, 2008 11:24 pm UTC

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

User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Re: Easy DDR-related puzzle

Postby Patashu » Tue Jun 03, 2008 12:25 am UTC

Solving DDR logic puzzles while playing DDR? I dunno, I think I still prefer people juggling while playing DDR :P (not that I can do it) (juggle that is)

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

Re: Easy DDR-related puzzle

Postby skeptical scientist » Tue Jun 03, 2008 3:33 am UTC

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

Postby Cauchy » Tue Jun 03, 2008 4:08 am UTC

The expected length of your combo before making your first mistake is [math]\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 =[/math][math]\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) =[/math][math]\left(n-1\right) - \left(\frac{n-1}{n}\right)^n\left(n-1\right) \approx n\left(1 - \frac{1}{e}\right)[/math]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.

User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Re: Easy DDR-related puzzle

Postby Patashu » Tue Jun 03, 2008 9:13 am UTC

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

User avatar
Godskalken
Posts: 159
Joined: Wed May 14, 2008 3:29 pm UTC

Re: Easy DDR-related puzzle

Postby Godskalken » Tue Jun 03, 2008 11:27 am UTC

Did noone else wonder what this puzzle had to do with der Deutschen Demokratischen Republik? I must be getting old.

User avatar
Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Re: Easy DDR-related puzzle

Postby Blatm » Thu Jun 05, 2008 4:18 am UTC

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.

User avatar
zed0
Posts: 179
Joined: Sun Dec 17, 2006 11:00 pm UTC

Re: Easy DDR-related puzzle

Postby zed0 » Thu Jun 05, 2008 11:06 pm UTC

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.

User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Re: Easy DDR-related puzzle

Postby Patashu » Fri Jun 06, 2008 12:33 am UTC

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! :evil:

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

Re: Easy DDR-related puzzle

Postby Xalerwons » Mon Jun 09, 2008 9:23 am UTC

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.

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

Re: Easy DDR-related puzzle

Postby meat.paste » Mon Jun 09, 2008 1:19 pm UTC

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

Postby Xalerwons » Wed Jun 11, 2008 6:50 pm UTC

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.

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

Re: Easy DDR-related puzzle

Postby meat.paste » Sun Jun 15, 2008 4:06 am UTC

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?


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 4 guests