Adventure Game Studio

Who needs more riddle threads?
Everyone!! :cheesy: :cheesy: :cheesy:

So I propose we play... combinatorics and probability!

Here's a fairly easy (and fairly tedious) permutation exercise to get things started:

5 new AGS games came out this week: Gabriel Knightley, Escape from the Wonky Island, Gyst, Oceanspirit Tennis and Day of the Ten Tacos.

You're really excited and want to play all of them today, one after another, but you want to leave the Wonky Island until last, and you want to play Oceanspirit Tennis as soon as possible, that is either first or second. In how many different ways can you play those games?


If you think you know the answer, post it together with some sort of explanation, either a proper mathematical one or just something you make up as you go along. I guess you could also use brute force while you can (which would be typing out all the possible combinations and then counting them).

---------
Also, if you don't know where to start, here's a cool site explaining the basics of combinations and permutations in an easy-to-understand manner:
http://www.mathsisfun.com/combinatorics/combinations-permutations.html

I stink at math, but my reasoning would run something like this:

• If Wonky Island is always last, it should be dropped from has no bearing on the number of possibilities we're considering.
• 
  If Oceanspirit is first or second, that means:
  
  
  
  • Three possibilities in the first slot with Oceanspirit in the second (A)
  • Three possibilities in the second slot with Oceanspirit in the first (B)
  • A combination of the others in third or fourth for each (C)
  • For each A, there are two C groups. For each B, there are two C groups.
• Therefore, (3x2)+(3x2)=12

My guess is 12, though I think it's unlikely I'm correct.

You're absolutely correct, of course! I think. :P

Spoiler

I solved it a bit differently, but we got the same result in the end.

There are 2 types of events we can treat separately, like you already indicated:
- OT is first: 1 x 3 x 2 x 1 x 1 = 6
- OT is second: 3 x 1 x 2 x 1 x 1 = 6
Which gives us: 6 + 6 = 12

[close]

(For future reference: if you notice any wrong answers being accepted, make sure to point it out, please.)

Eric, do you want to come up with the next one? It can also be a probability-type riddle.

Oooh...I don't know if I'm up to that. Why don't you give us another one, and I'll try to think of one for the future?

you have these feelings again and are really emotional on the internet today because you want to share these emotions.
But to not have smiley spammers, the forum admin has limited the number of smileys to 3 per post.
How many different ways are there to express your important emotions with a set of 20 smileys?

O0

Quote from: selmiak on Sat 04/04/2015 11:46:25
you have these feelings again and are really emotional on the internet today because you want to share these emotions.
But to not have smiley spammers, the forum admin has limited the number of smileys to 3 per post.
How many different ways are there to express your important emotions with a set of 20 smileys?

O0

(wtf) :-D 8-)


In the meantime, let's have another one in hardcore mode.

If you throw a standard die 5 times in a row, what's the probability of:
a) the die showing the same number every time?
b) forming a streak of 3 or more of the same number?

A

Spoiler

1 in 6^5 or 1 in 7776  or  0.0001286 (.01286%)

[close]

?

Quote from: mkennedy on Sat 04/04/2015 23:43:47

Spoiler

1 in 6^5 or 1 in 7776  or  0.0001286 (.01286%)

[close]

Cool, you're going in the right direction... but there's still something missing!

What about Selmiak's smiley challenge, anyone who can tackle that one?
Also, if anyone wants to add their own combinatorics/probability problem, be my guest! It's not even required to know the answer beforehand. ;)

Quote from: Cuiki on Sun 05/04/2015 00:57:07

Quote from: mkennedy on Sat 04/04/2015 23:43:47

Spoiler

1 in 6^5 or 1 in 7776  or  0.0001286 (.01286%)

[close]

Cool, you're going in the right direction... but there's still something missing!

Doh!

Spoiler

Multiply it by 6 for 6/(6^5) or  1 in 1296 or .000771604 or .0771604%

[close]

Been long time since I took probability in college. Hopefully this time I got it right.

Yep, that's it!

Quote from: Cuiki on Mon 06/04/2015 15:16:05
Yep, that's it!

Isn't that actually the probability of the 5 throws showing a specific pre-determined number 5 times in a row?

The problem only said "the same number 5 times in a row"...In this case: The first throw is irrevelant, the number can be anything and only serves to define the number which must be thrown another 4 times.

For example:

The chance of throwing two sixes in a row is 1 in 36.

But the chance of throwing the same number twice in a row is 1 in 6, as the second throw only needs to match whatever the first throw was.

Or maybe I'm missing something?

Mandle, that's correct, and if you take into account MKennedy's 2nd post, you'll find that the results are the same.

His approach was to find out the probability of getting a specific number 5 times in a row, then multiplying by 6 to get all the possibilities.

PS:
Here's another one:

Roll a standard die. If you roll 6 it means you get a reroll (adding the 6 you already rolled). This can, theoretically, go on forever. What's the average result of rolling this die?

Yeah, like Andail said.
To further elaborate (also for other people who aren't entirely sure what's going on):

Mkennedy's approach looks something like this:

The number of all the possible outcomes is 6x6x6x6x6 or 6^5 or 7776.
The number of desired outcomes is 6 ([1,1,1,1,1] or [2,2,2,2,2] or [3,3,3,3,3] or [4,4,4,4,4] or [5,5,5,5,5] or [6,6,6,6,6])

When you divide the number of desired outcomes with the number of total outcomes, it shows you the likelihood of a desired event to happen in the form of a number between 0 and 1 (0 being impossible and 1 being certain).

So, we have 7776 different ways in which this die can land, but only 6 of them will yield the desired outcome. 6 divided by 7776 is 0.00077 (or 0.077%, if you multiply it by 100).
----
Now, what you were doing on the other hand, was not calculating the number of outcomes in advance, but rather figuring out the probability of each individual throw and multiplying them together in the end (which is an equally valid approach):

- the first throw can of course be any number from 1-6, which translates to 6/6 chances (or 1)
- the second throw can only be one specific number (determined by the previous throw), so we have 1/6 chances to get this one right.
- same with the third, fourth and fifth throw.

So, in the end, our calculation would look like this:
(6/6) x (1/6) x (1/6) x (1/6) x (1/6) = 6/7776 = 0.00077
OR:
1 x (1/6) x (1/6) x (1/6) x (1/6) = 1/1296 = 0.00077

Apologies for a double post...

Quote from: Andail on Tue 07/04/2015 14:47:07
Roll a standard die. If you roll 6 it means you get a reroll (adding the 6 you already rolled). This can, theoretically, go on forever. What's the average result of rolling this die?

Wow, that one is pretty insane. :shocked:
But I guess it's a sort of thing that could occasionally come in handy in real life situations (board games, maybe?), so let's give it a go.

Spoiler

For the sake of simplicity, let's say we have a really limited number of rerolls before someone tells us: "That does it. You're cheating, there's no way anyone could have so much luck."

First, let's limit it to 1 reroll. The equation would go something like this:
(http://img.photobucket.com/albums/v467/missy_L/CodeCogsEqn1.png)

And if it's limited to 2 rerolls, it would look like this:
(http://img.photobucket.com/albums/v467/missy_L/CodeCogsEqn2.png)

Can you see the pattern? The numbers at the top of the fractions (numerators?) are all the scores you can get. Basically, if the player is allowed to do a maximum of two rerolls, your scores can be 1, 2, 3, 4 and 5 but not 6; they can be 7, 8, 9, 10 and 11 but not 12 (6 + 6); and they can be 13, 14, 15, 16, 17, AND 18 (6 + 6 + 6). Makes sense?

Anyway, the average gets slightly bigger with each reroll.
So, the average score would be 4.19991 for when the rules allow you to do 5 rerolls (meaning a total of 6 rolls).

[close]

Spoiler

But that's not good enough, eh? :tongue:

So I tried to come up with a more general formula. I can't really explain how I got there, but let's just say it took quite a bit of trial and error.
(http://img.photobucket.com/albums/v467/missy_L/CodeCogsEqn.png)
n = number of rerolls allowed.

It looks kinda messy, but that's really about as good as I can make it. Besides, I only ever tested it with small values for n. Anyone feels like doing a double check?

[close]

Spoiler

So, unless I completely screwed up somewhere along the way (which I certainly might have), the answer should be: somewhere around 4.2
TA-DA!

And now I've got a headache...

[close]

EDIT: I uploaded a wrong formula before.

but, ... but I never rolled a 4.2 ever ???

Yeah, that's where it all falls apart.. :tongue:

Ahhhhhh...gotcha...I didn't understand how the "desired results sets" thing worked. My probability studies only went as far as the very basics it seems. I'd imagine the more complex methods being shown here are far more robust and can tackle more intricate problems.

That last one looks more like the calculations for a shuttle launch to me than something to do with a mere d6 :=

The average dice roll is 3.5 (7/2). The chance of getting another roll is 1/6. So the total is the sum of all terms 3.5 * (1/6)^k, where k goes from 0 to infinity. There's some formula to calculate the sum of a (convergent) infinite series that I used to know, but have forgotten. Ah, here it is:

http://www.mathsisfun.com/algebra/sequences-sums-geometric.html

For a series of the form a*r^k, the sum is a*(1/1-r).

So the answer is 3.5 * 6/5 = 7/2 * 6/5 = 21/5 = 4.2.

I get the feeling you are all cheating. I'll never play any games with you that involve any dice! :P

QuoteSo the answer is 3.5 * 6/5 = 7/2 * 6/5 = 21/5 = 4.2.

Oh man, I should have known there was an easier way to solve that! XD
(Btw, I'm really useless at maths in general. It's just these combinatorics-type problems that I adore for some reason...)

---------------------------------------
Okay, here's a little game:

There are 6 marbles in a bag.
(http://img.photobucket.com/albums/v467/missy_L/marbles1.png)

One of them is worth 10 points, two are worth 5 points, two are worth 1 point, and one has an X written on it, meaning it will deduce all the points from you if you draw it.
You can draw as many as you wish, and if your total score is 10 points or more, you'll get paid double the amount of money you bet, and if you lose, you lose all of it.

a) How many marbles should you draw in order to have the highest possible chances of winning?
b) Is it a reasonable game to play (i.e. would you be making more money than losing it in the long run)?

Quote from: Cuiki on Wed 08/04/2015 23:09:33
(http://img.photobucket.com/albums/v467/missy_L/marbles1.png)
You can draw as many as you wish, and if your total score is 10 points or more, you'll get paid double the amount of money you bet, and if you lose, you lose all of it.

a) How many marbles should you draw in order to have the highest possible chances of winning?
b) Is it a reasonable game to play (i.e. would you be making more money than losing it in the long run)?

Not a math guy, but I'll try to solve it backwards:


b)  The odds are against you.  You have a 1/6 chance of outright victory (10 points) and 1/6 chance of instant defeat (x), cancelling each other out.  The ones are useless because they will never combine to make ten points (and playing past 10 is insane).  There is a 1/30 chance from the outset of getting two fives (1/6 * 1/5), but a much higher chance of drawing an x over two draws (if I'm not mistaken, 1/6 + 1/5 or 11/30).  The odds get further apart if you draw more than twice.

a)  The highest possible chance of winning is therefore drawing once (50:50).  Anything more than that the odds become progressively stacked against you.

Edit:  Gah, that's not right, since 1/6 + 1/5 + 1/4 + 1/3 + 1/2 guarantees failure, but of course it is possible to draw five marbles. :P

I believe this might be similar to the 'finding a good toilet' problem?

http://youtu.be/ZWib5olGbQ0

My answer..

a) 3 marbles gives you the best chance (40%) of a good outcome.

For 1, 2, 4, and 5 marbles, the chances of a good outcome respectively are 1/6, 1/3, 1/3, 1/6

My method was just grouping the possibilities and counting them. I've forgotten the formulas. :(

b) Given you know to pick 3 marbles, it's a reasonable game because 40% is not bad. It's nearly 50%

I'm assuming in this game you draw all the marbles at once, not one at a time and then deciding what to do next?

If so, we can answer the second part without doing any real probability calculations.

The payout is double or nothing, so you need at least a 50% chance of winning in order to make money in the long run.

If you draw three marbles or more, you have at least a 50% chance of drawing the X, so that can't be a winning strategy. If you draw one marble you obviously have a 1/6 chance of winning. So the only possible worthwhile strategy is to draw two and hope you get the 10 (and not an X), or two 5s. We know this is not going to happen more than 50% of the time by symmetry: it must be equal to the chance of drawing the X (and not the 10) or two 1s.

So no, it's not a reasonable game.

Quote from: Cuiki on Wed 08/04/2015 23:09:33
You can draw as many as you wish, and if your total score is 10 points or more, you'll get paid double the amount of money you bet, and if you lose, you lose all of it.

I interpret this as win or loose. If the marbles add up to at least 10 and exclude marble 'X' then you win.

This is how I approached the problem:

Spoiler

(http://www.mediafire.com/convkey/40c7/2u99aaase98sy97zg.jpg)

[close]

So the answer is:

a) Pick 3 marbles

b) Given you know to pick 3 marbles then you'll have a 40% chance of a win.

It is a 40% chance each time you play. The odds aren't too bad.

Edit: Made a few errors before with the total combinations.. now fixed. Thank-you online Combinations Calculator!

;)

That's a very... thorough approach. I always look for shortcuts to avoid having to do any counting/calculations whenever possible.

If you think 40% are acceptable odds on a double-or-nothing bet, I'd be happy to bet against you! In any case, the question defined "reasonable" as "would you be making more money than losing it in the long run," and so the answer is no, you won't.

However, if you draw the marbles one-by-one and decide whether to stop or continue, then the game is in your favor.

Spoiler

Consider: If you draw the 10 you have won, if you draw the X you have lost. The chances of drawing one or the other are always equal (as Baron says, they "cancel out").  If you draw any other marble, you have either won (if you now have two 5s), or you get to play again. The total chance of winning is the likelihood of getting a 10, plus the likelihood of getting the second 5, plus the likelihood of getting to play again times the likelihood of winning in a future round. Conversely, the chance of losing is the likelihood of drawing an X, plus the likelihood of getting to play again times the likelihood of losing in a future round. These probabilities, of course, must add up to 1.

If you manage to draw four marbles without getting the X, you're guaranteed to have more than 10 points, so you've won. Once you have three marbles, the chance of getting the X on your fourth draw is 1/3, so you have a 2/3 chance of winning.

Now it's easy to see that the chance of losing must always (in every round) be smaller than the chance of winning, since the chance of losing consists of two terms, each of which is balanced by an equal or greater term on the winning side:
-The chance of drawing an X now (which is equal to the chance of drawing a 10 now)
-The chance of losing in a future turn (which is smaller than the chance of winning in a future turn)

Why is the chance of winning in a future round always greater than the chance of losing? Because we know that you have a 2/3 chance of winning in the fourth round, so in the third round the future win term is bigger than the future loss term, and so the chance of victory in or after the third round is >50%. But now we can apply the same argument to the second round, and then in turn to the first round. And that's our proof by induction.

[close]

So you have a better than 50% chance of winning, and will make money in the long run.

RE: One-ball-at-a-time version:

Actually, if all you want to know is whether your odds are 50:50 or better, then it's even simpler to work out:

Spoiler

Since the odds of drawing a 10 at any point are equal to the odds of drawing an X, and there are other ways to win besides drawing a 10 but no ways to lose besides drawing an X, then the odds of winning must necessarily be better than 50:50.

[close]

In any case, it's pretty easy to calculate the actual odds:

Spoiler

It's easy to count the possible ways we can lose:

We have to draw an X in any of the first four rounds.

X in first round = 1 possibility
X in second round = 4 possibilities (drew a 5 or 1 in round 1)
X in third round = 10 possibliities (drew 5-1-X, 1-5-X, or 1-1-X, of which there are 4, 4, and 2 versions respectively)
X in fourth round = 12 possibilities (drew 5-1-1-X, 1-5-1-X, or 1-1-5-X, of which there are 4 versions each)

So there's 27 ways to lose.

Note that the same pattern applies to winning by drawing a 10, so there's 27 ways to win with a 10. Already that's 50:50, but since we can also win by drawing two 5 balls, we know that it's better than 50:50. How much better?

Well, how many ways are there to win by drawing two 5 balls?

It must be in round 2 or later, and the other balls must include the other 5 and the rest must be 1 balls.

To win in round 2, the draws must be 5-5, but you could do it in either order. So that's 2 possibilities for round 2.
To win in round 3, the draws must be 5-1-5 or 1-5-5, and for each of these you could have drawn either of the 1 balls (so there's 2 permutations now for each draw order), and the 5 balls could have been drawn in either order (4 permutations for each draw order, then). That makes 8 possibilities for round 3.
To win in round 4, the draws must be 5-1-1-5, 1-5-1-5, or 1-1-5-5, and for each of these the 1 and 5 balls could be drawn in either order (4 permutations for each draw order). So that's 12 possibilities for round 3.

That makes 2+8+12=22 ways to win by drawing both 5 balls.

27+27+22=76 possible outcomes.
27+22=49 winning outcomes.

49/76 = 0.6447 so we have about a 64.5% chance to win.

[close]

Here's another:

Suppose you have three distinct tile types (â””, â•š, and â”Å") and want to construct a 2x2 arrangement of these tiles such that there is either horizontal, vertical, or rotational symmetry. How many possible arrangements of these three tile types qualify? You can assume that rotations and flipped versions of arrangements are distinct arrangements (assuming that they are actually different when rotated or flipped).

Example:
┐â”Å'
┘└ has symmetry over both axes.

┬┤
â”Å"â”´ has rotational symmetry, because if you turn it 90°, 180°, or 270° it will look the same as before you turned it.

Looks good Erenan. I'll check that out a bit later.

Quote from: Snarky on Thu 09/04/2015 15:47:15
If you think 40% are acceptable odds on a double-or-nothing bet, I'd be happy to bet against you! In any case, the question defined "reasonable" as "would you be making more money than losing it in the long run," and so the answer is no, you won't.

Fair enough. Just as well I'm not a gambling man!

Back to selmiak's cup problem..

Quote from: selmiak on Sat 04/04/2015 11:46:25
you have these feelings again and are really emotional on the internet today because you want to share these emotions.
But to not have smiley spammers, the forum admin has limited the number of smileys to 3 per post.
How many different ways are there to express your important emotions with a set of 20 smileys?

The number of combinations is

C(n,r) = n! / ( r! (n - r)! )

Where
n = total number of distinguishable objects
r = sample size

So for 20 different mug emoticons (n = 20) and 3 selections (r = 3) therefore... (waiting... online combinatorics calculator in process...) ahem, the answer is 1140

<insert nerdy emoticon>

Here's another problem involving mugs..

I'm feeling ambivalent today. I have 5 :) and 4 :-D and 3 (http://www.vanwijst.com/games/smileys/baron_cup.gif) at my disposal.

How many different ways can I arrange all those mugs in a line?

:) :) :) :) :) :-D :-D :-D :-D (http://www.vanwijst.com/games/smileys/baron_cup.gif) (http://www.vanwijst.com/games/smileys/baron_cup.gif) (http://www.vanwijst.com/games/smileys/baron_cup.gif)

But wait. That's assuming the order of the three smileys doesn't matter. If :X :-\ :-[ is equivalent to :-[ :-\ :X for instance. But surely those express two different things, no? I would imagine the true number of combinations would be 20*20*20 if you can repeat smileys or 20*19*18 if you cannot. BTW, you get the same result that you calculated before if you just do 20*19*18/6 (20*19*18 is the number of ways you can choose 3 out of 20 smileys, and you divide by 6 to account for the six permutations of three distinct objects).

Wow, great work, people :)

QuoteI'm assuming in this game you draw all the marbles at once, not one at a time and then deciding what to do next?

Oh... I'm sorry about the confusion.
I meant drawing all the marbles at once, but the other way around sounds even more interesting.

Erenan, That was a really classy approach. :D

Spoiler

I got to a vaguely similar result (0.6333) by figuring out the probability of winning in each of the first 4 stages (1/6 + 1/5 + 1/5 + 1/15), but my approach was just generally more confusing and time consuming, so if either one made a mistake, it was definitely me. :P

[close]

About the cup problem:
You can use 3 smileys at most, but what if you feel like using less than that? Perhaps even none? ;)

Quote from: Erenan on Thu 09/04/2015 23:01:25
Suppose you have three distinct tile types (â””, â•š, and â”Å") and want to construct a 2x2 arrangement of these tiles such that there is either horizontal, vertical, or rotational symmetry. How many possible arrangements of these three tile types qualify? You can assume that rotations and flipped versions of arrangements are distinct arrangements (assuming that they are actually different when rotated or flipped).

Example:
┐â”Å'
┘└ has symmetry over both axes.

┬┤
â”Å"â”´ has rotational symmetry, because if you turn it 90°, 180°, or 270° it will look the same as before you turned it.

This one was really fun. :)
But I can't tell at all if I got it right or not...

Spoiler

I hope I hadn't completely misinterpreted the rules... You can use different tile types within the same arrangement, right?

And when it comes to rotational symmetry, I'm not sure it's possible to make a pattern that would work for 90°or 270° - not with these symbols anyway, and not with these line breaks. But either way I don't think it would affect the end result, so it shouldn't matter.

A few rules:
Horizontal: Top row is symmetrical. Bottom row is symmetrical. Top and bottom rows can be completely different:
╚╝    ┬┬    ┘└    â•â€"â•”
â”´â”´    â•”â•â€"    ┘└    ┤â”Å"

Vertical: Left column is symmertrical. Right column is symmetrical. Left and right columns can be completely different:
┬┴    ╝┤    ┘┘
┴┬    â•â€"┤    ┐┐

Rotational: Top left tile is a 180° rotation of bottom right tile. Top right tile is a 180° rotation of bottom left tile. Adjacent tiles can be completely different, only diagonal ones matter:
┐┘    ┴╝    ╔╔
â”Å'â””    ╔┬    ╝╝

Overlap: 2-way symmetrical patterns mean overlap of all three categories â€" horizontal, vertical and rotational. They can only occur when all the tiles are part of the same set:
â•â€"â•”    ┬┬    └┘
╝╚    â”´â”´    â”Å'┐



Horizontal: 12 top-row variations x 12 bottom-row variations = 144
Vertical: 12 x 12 = 144
Rotational: 12 x 12 = 144
2-way symmetrical: 3 x 4 = 12

3 x 144 - 2 x 12 = 408 total

(I substracted 2 x 12 to compensate for all the excess overlap: as one and the same 2-way symmetry pattern appears 3 times (in horizontal, vertical and rotational category) but it should really be counted only once.)

[close]

If an infinite number of monkeys typed randomly on an infinite number of typewriters how long would it take at least one of them to correctly type out a specific pre-existing text containing 1,000,000,000 characters (letters,numbers,etc.) assuming that they all started typing at the same time and all had the exact same typing speed of one keystroke per second?

Bonus Question: At the exact same time as at least one monkey completed the text flawlessly how many other monkeys would also complete it?

(I just thought I'd throw a pretty easy one in to give some non-mathemathical geniuses a shot, so if the answer is obvious to you at first glance then maybe just say "solved" and give someone else a chance? Or not...)

Well... at least one monkey would have to named Shakespeare of course :P but I would have thought...

Spoiler

With infinite monkeys, it should take one of them 1,000,000,000 seconds (31 years and approx 8 and a half months) as theoretically at least one of them would accomplish this.

For the bonus question, I would also answer an infinite amount.  Although depending on the number of potentially different keystroke combinations available you could come up with a number (assuming 26 letters in upper or lower case, 10 numerals, 5 punctuation marks and blank space would give you 68^1,000,000,000), infinity divided by any finite number is still infinity (though it could I suppose be expressed as a theoretical number ∞/n), as ∞ cannot be quantified, I would expect it to still be ∞).

[close]

Those are my ramblings, anyway.

Quote from: CaptainD on Fri 08/05/2015 17:18:08
Well... at least one monkey would have to named Shakespeare of course :P but I would have thought...

Spoiler

With infinite monkeys, it should take one of them 1,000,000,000 seconds (31 years and approx 8 and a half months) as theoretically at least one of them would accomplish this.

For the bonus question, I would also answer an infinite amount.  Although depending on the number of potentially different keystroke combinations available you could come up with a number (assuming 26 letters in upper or lower case, 10 numerals, 5 punctuation marks and blank space would give you 68^1,000,000,000), infinity divided by any finite number is still infinity (though it could I suppose be expressed as a theoretical number ∞/n), as ∞ cannot be quantified, I would expect it to still be ∞).

[close]

Those are my ramblings, anyway.

Your answer is 100% correct...

Also you said "at least one monkey would have to named Shakespeare"...

EXTRA BONUS QUESTION: In this problem how many of the monkeys would have been named "Shakespeare" given that every monkey was assigned a name consisting of random characters of variable lengths between one (1) character and one hundred and fifty seven (157) characters with no truncating allowed for the last characters being filled entirely by blank spaces?

Spoiler

Infinitely many, of course. There's a finite number of names for an infinite number of monkeys (assigned randomly), so each one is used infinitely often. And an infinite number of these monkeys (named Shakespeare) will type out the predefined text on their first try.

[close]

Well done Snarky as well! Damn limber-minded people we have here at AGS!

Man, infinity is so mind-boggling, isn't it?
I wonder if it exists at all, outside mathematics...

Anyway, here's one probability problem I posted earlier on in the thread, but perhaps it was worded a bit strangely:

If you throw a die 5 times, what is the likelihood of getting the same number (at least) three times in a row?

Quote from: Cuiki on Mon 11/05/2015 12:16:24
If you throw a die 5 times, what is the likelihood of getting the same number (at least) three times in a row?

Spoiler

Is this a trick question?  It would depend on the number of sides the dice had.  If we assume a 6-sided dice, the probability would be quite simple - 6^3 = 1:216.  But that's just based on getting it in 3 rolls.  But we'd had to multiply that by 3, as you could potentially start the 3x roll on the 1st, 2nd or 3rd roll. So that would make it 3:216 or 1:72.

But then you'd have to add in the probability of getting 4 in a row (twice) and 5 in a row (once).  So that would be 2:1296 + 1:7776.   Putting that all together, unless I've made a mistake, gives you an overall probability of 121:7776.

[close]

Spoiler

A couple of mistakes in that calculation, CD. First of all, the chance of getting the same number three times in a row is 1/6^2 (the first throw doesn't count because we don't specify which number you have to get, so anything you throw is fine). Secondly, the calculation of the chance of getting three in a row already includes the chance of then getting four or five in a row, so you shouldn't add those separately. So the total probability is, I believe, 3/36=1/12. (Actually, on second thought you need to subtract the four-in-a-row and five-in-a-row terms, because they're implicitly included multiple times: in each of the three-in-a-row conditions. So it's slightly lower. Can't be bothered to do the numerical calculation.)

[close]

Ah yes... should have realised all of those things Snarky!  :-[

A trick question? What do you take me for? :P

Spoiler

Personally, I find it really helpful to draw empty slots to represent individual rolls (like this: __ x __ x __ x __ x __), and fill them in with the number of possible outcomes for each (plus a bit of multiplying in the end to compensate for all the different positions they can take).

So for example, exactly 3 in a row of the same number would look like:
(6 x ( 1 x 1 x 1 x 5 x 6) x 2) + (6 x (5 x 1 x 1 x 1 x 5))
Sounds right?

What about 4 and 5 in a row?

[close]

Aha, I got one! This is what you might call a problem from real life (which means I don't know the answer off the top of my head)...

I have a 4-wheel combination lock for my bike. Each wheel has 10 different possible positions (0-9):

(http://i.imgur.com/XysKQMq.jpg?1)

Let's say my code is 1234. When I lock it, I spin each wheel into a random position. I want to be able to unlock it with as little effort as possible. To simplify a bit, let's say that "effort" is measured in how much I have to turn each wheel. (So if I have to turn the first wheel 3 positions, the second 4, the third 1 and the fourth 2, the total effort is 3+4+1+2=10.)

Obviously, if I just set the wheels one-by-one, the worst-case scenario is that I have to turn each wheel 5 positions, so the total effort is 4*5=20. On average it will be half that, 10 (2.5 per wheel). However, if I grip the wheels a little differently, I can actually just as easily turn two (adjacent) wheels at a time. (Three is possible but more trouble than it's worth, so let's ignore that.) This changes things significantly, because if I, like in the above example, see that I have to turn the first wheel three positions and the second 4 (in the same direction), I can turn them 3 positions together, and then I just have to turn the second wheel 1 position.

So here's the challenge:

1. What is the worst-case and the average effort now (for the most efficient way to solve the lock from any random start position)?
2. Can you come up with an algorithm to work out the optimal way to solve the lock (which moves to do in which order) from any start position?

All right, I'll have a go at at least part of the problem, then. For simplicity and without loss of generality, let's now say that the code is 0000. So the number of turns (degree of rotation) needed to put it a wheel in the right position from each starting position are:

0:0
1:1
2:2
3:3
4:4
5:5
6:4
7:3
8:2
9:1

(Notice that we have symmetry around 5: 6 and 4 are equivalent, as are 7 and 3, 8 and 2, and 9 and 1.)

Let's start by putting some upper and lower bounds on the worst-case scenario.

Clearly, the amount of work can't be greater than if you're turning the wheels individually, so an upper bound on the maximum effort needed is 20. To establish a lower bound, we can divide up the problem into steps, and first just look at what it would take to get the two wheels on the ends (X--X) in position. Since there's no interference between them, it doesn't matter if we turn them by themselves or together with one of the other wheels, in the worst case it's still 5 per wheel, 10 total. That gives us a lower bound.

We can now proceed to tighten these bounds. Let's add one of the wheels in the middle into consideration (XX-X). Now the wheel to the right is still independent (there's no way to have its turning affect or by affected by the other wheels we're considering), so we can just look at positioning the two wheels on the left together. The approach we'll consider is to start by turning the first wheel into position, either by itself or with the other one depending on whether it will improve the starting position of the second wheel, and then turn the second wheel into position. Because of symmetry and because rotation is commutative, this is equivalent to any other approach.

The cost of positioning the first wheel is still 0-5. The cost of the final turn to adjust the second wheel, though, depends on how much we turned the first wheel (and therefore optionally the second along with it). So, for example if the second wheel started out at 5, any turn at all would reduce the remaining turns needed by that same amount (turn it 4 and there's only 1 left, turn it 3 and there are 2 left, etc.), so the max cost is 5 - cost_of_first wheel, and the total cost of them both is always 5.

So if we think about how many turns we can make at most (up to 5) that leaves us in a worse (or equivalent) starting position, for each of the starting positions of the second wheel, we get:

0:5 (-> 5)
1:5 (-> 6)
2:5 (-> 7)
3:4 (-> 7)
4:2 (-> 6)
5:0 (-> 5)
6:2 (-> 4)
7:4 (-> 3)
8:5 (-> 3)
9:5 (-> 4)

So the max cost of both wheels together is 7 (5+2 or 4+3). So the max cost of setting three wheels (XX-X) is 7+5=12, which is also a lower bound on the cost of setting all four. Now we can use a similar argument with the two wheels on the right, to show that an upper bound on the max cost of all four wheels is 14.

Hmmm... I think I'll leave it there for now. The worst-case cost is somewhere between 12 and 14, but establishing the precise figure gets a bit more complicated, because we have to consider possible interactions between the wheels in the middle as well.

2 words

Bolt cutters

100% success rate (laugh)