Thread Rating:

Poll

15 votes (53.57%)
11 votes (39.28%)
5 votes (17.85%)
2 votes (7.14%)
8 votes (28.57%)
3 votes (10.71%)
5 votes (17.85%)
4 votes (14.28%)
10 votes (35.71%)
7 votes (25%)

28 members have voted

ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 100
  • Posts: 4778
June 11th, 2021 at 12:20:20 PM permalink
Quote: Joeman

This was a toughie. I kept coming up with 6 move solutions until I realized that white's knight had to wait until black's rook passed to move.

1. g4 h5
2. Bg2 h5xg4
3. Bxb7 Rxh2
4. Nh3 Bxb7
5. O-O Rh1++

A very odd set of moves for both sides!


When I first saw it, I didn't think it was possible, until I discovered...

...that you are allowed to castle even when your rook is being attacked - it's just the king (or the spaces the king traverses) that can't be attacked.

ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 100
  • Posts: 4778
June 11th, 2021 at 1:18:09 PM permalink
Quote: Ace2

Assuming an infinite standard deck of cards, you draw until you have all thirteen cards of any suit (diamonds, hearts, spades or clubs).

On average, how many draws will it take?



47,070,163,786,203,595,393,879,102,723 / 1,237,940,039,285,380,274,899,124,224, which is about 38.

EdCollins
EdCollins
Joined: Oct 21, 2011
  • Threads: 18
  • Posts: 1291
June 11th, 2021 at 2:40:42 PM permalink
If the original question is changed from this:

Using only pennies, nickels, dimes, quarters, half dollars, $1 bills, $5 bills, and $10 bills, what is the most money that you can have without being able to change a $20 bill?

to this:

Using only current U.S. currency $10 and under, and current U.S. coin denominations, what is the most money you can have without being able to change a $20 bill?

what is the answer?
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 33
  • Posts: 2372
June 11th, 2021 at 2:46:17 PM permalink
Quote: EdCollins

... Using only current U.S. currency $10 and under, and current U.S. coin denominations, what is the most money you can have without being able to change a $20 bill?...what is the answer?

$23 being $5 $5 $5 $2 $2 $2 $2 would be a different answer, and that's ignoring the pennies part!

btw I think you might need to have some reference to exactly change $20.
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 23
  • Posts: 925
June 11th, 2021 at 3:02:19 PM permalink
Quote: ThatDonGuy


47,070,163,786,203,595,393,879,102,723 / 1,237,940,039,285,380,274,899,124,224, which is about 38.

I disagree. My answer is significantly higher than yours.

I did a basic simulation in excel and there is only about a 1 in 3,000 chance of success with that many draws
Itís all about making that GTA
gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 46
  • Posts: 2889
June 11th, 2021 at 6:40:11 PM permalink
Quote: Ace2

Quote: ThatDonGuy


47,070,163,786,203,595,393,879,102,723 / 1,237,940,039,285,380,274,899,124,224, which is about 38.

I disagree. My answer is significantly higher than yours.

I did a basic simulation in excel and there is only about a 1 in 3,000 chance of success with that many draws



I agree that ThatDonGuy's answer seems to be too low - and only by doing calculations in my head, not on my computer. I wonder if ThatDonGuy mis-read the problem in some way.

I'm away from my number-grinding CPU system, so no math: But with full replacement, if you have drawn 38 cards, how many distinct cards do you expect to have drawn? I don't know, maybe 30-32? And if you have 30-32 cards out of a possible 52, what is the liklihood that you have all 13 cards from one of the 4 suits? Not very good.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 100
  • Posts: 4778
June 11th, 2021 at 7:01:23 PM permalink
Quote: Ace2

Quote: ThatDonGuy


47,070,163,786,203,595,393,879,102,723 / 1,237,940,039,285,380,274,899,124,224, which is about 38.

I disagree. My answer is significantly higher than yours.

I did a basic simulation in excel and there is only about a 1 in 3,000 chance of success with that many draws


I did read the problem wrong. The number I got is how many it takes to get 13 cards of any suit, regardless of ranks.

And here is the correct answer:

712,830,140,335,392,780,521 / 6,621,889,966,337,599,800, or about 107.64753627

If you limit it to a single 52-card deck, it takes 28,561 / 630 = 45.335 cards.

Last edited by: ThatDonGuy on Jun 12, 2021
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 23
  • Posts: 925
June 12th, 2021 at 10:18:11 AM permalink
Quote: ThatDonGuy

Quote: Ace2

Quote: ThatDonGuy


47,070,163,786,203,595,393,879,102,723 / 1,237,940,039,285,380,274,899,124,224, which is about 38.

I disagree. My answer is significantly higher than yours.

I did a basic simulation in excel and there is only about a 1 in 3,000 chance of success with that many draws


I did read the problem wrong. The number I got is how many it takes to get 13 cards of any suit, regardless of ranks.

And here is the correct answer:

712,830,140,335,392,780,521 / 6,621,889,966,337,599,800, or about 107.64753627

If you limit it to a single 52-card deck, it takes 28,561 / 630 = 45.335 cards.

That is correct. Please show your method
Itís all about making that GTA
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 100
  • Posts: 4778
June 12th, 2021 at 10:39:33 AM permalink
Quote: Ace2

That is correct. Please show your method


Brute force / Markov chain.
Let E(s,h,c,d) be the expected number of cards needed when you already have s different spades, h different hearts, c different clubs, and d different diamonds.
Note that this is 0 if any of the numbers are 13.
Of the 52 cards:
(13 - s) will be a spade you didn't draw yet, so you will move to state (s+1, h, c, d)
(13 - h) will be a heart you didn't draw yet, so you will move to state (s, h+1, c, d)
(13 - c) will be a club you didn't draw yet, so you will move to state (s, h, c+1, d)
(13 - d) will be a diamond you didn't draw yet, so you will move to state (s, h, c, d+1)
The remaining (s + h + c + d) cards will be cards you have already drawn, so you will remain at state (s, h, c, d)
Since it is an infinite deck, each card always has a 1/52 chance of being drawn.
E(s, h, c, d) = 1 + (13 - s) / 52 x E(s+1, h, c, d) + (13 - h) / 52 x E(s, h+1, c, d) + (13 - c) / 52 x E(s, h, c+1, d) + (13 - d) / 52 x E(s, h, c, d+1) + (s + h + c + d)/52 x E(s, h, c, d)
(52 - (s + h + c + d)) x E(s, h, c, d) = 52 + (13 - s) x E(s+1, h, c, d) + (13 - h) x E(s, h+1, c, d) + (13 - c) x E(s, h, c+1, d) + (13 - d) x E(s, h, c, d+1)
E(s, h, c, d) = (52 + (13 - s) x E(s+1, h, c, d) + (13 - h) x E(s, h+1, c, d) + (13 - c) x E(s, h, c+1, d) + (13 - d) x E(s, h, c, d+1)) / (52 - (s + h + c + d))
Start with calculating E(12, 12, 12, 12), then E(12, 12, 12, 11), and so on to E(12, 12, 12, 0), then E(12, 12, 11, 12), E(12, 12, 11, 11), and so on, until you finally get E(0, 0, 0, 0), which is the solution.

In the single-deck version, there are 52 - (s + h + d + c) cards left at any point, and drawing a duplicate is impossible:
E(s, h, c, d) = 1 + (13 - s) / (52 - (s + h + c + d)) x E(s+1, h, c, d) + (13 - h) / (52 - (s + h + c + d)) x E(s, h+1, c, d) + (13 - c) / (52 - (s + h + c + d)) x E(s, h, c+1, d) + (13 - d) / (52 - (s + h + c + d)) x E(s, h, c, d+1)
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 23
  • Posts: 925
June 12th, 2021 at 11:29:52 AM permalink
You can also get the answer by integrating the following formula over all t:

(1-(1-1/e^(t/52))^13)^4 dt

Which gives us the answer of 712830140335392780521 / 6621889966337599800 =~ 108 draws

Starting from the middle, 1/e^(t/52) is the probability at any time t that any single card has not been drawn. The complement of that to the 13th power (1-1/e^(t/52))^13 is the probability that all 13 cards of any one suit have been drawn at least once. The complement of that to the 4th power (1-(1-1/e^(t/52))^13)^4 is the probability that none of the 4 suits meet that condition (of all 13 cards being drawn at least once).

The formula works due to one of the most useful properties in probability: the expected time for an event to happen is equal to the sum of the probabilities over all time that it has not happened yet. This is basically the geometric series 1 + r + r^2 + r^3...= 1 / (1-r) carrying over from the binomial distribution to the exponential one.
Itís all about making that GTA

  • Jump to: