Combinatorics and Probability Riddles

[Baron]

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.

[monkey424]

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%

[Snarky]

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.

[monkey424]

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

[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!

[Snarky]

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.

[Erenan]

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.

[monkey424]

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

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..

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 and 3 at my disposal.

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

[Erenan]

But wait. That's assuming the order of the three smileys doesn't matter. If is equivalent to 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).

[Cuiki]

Wow, great work, people

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?

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.

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.

[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?

[Cuiki]

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]

[Mandle]

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...)

[CaptainD]

Well... at least one monkey would have to named Shakespeare of course 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.

[Mandle]

Well... at least one monkey would have to named Shakespeare of course 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?

[Snarky]

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]

[Mandle]

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

[Cuiki]

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?

[CaptainD]

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]

[Snarky]

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]

[CaptainD]

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

[Cuiki]

A trick question? What do you take me for?

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]