Thread Rating:

Poll

16 votes (50%)
12 votes (37.5%)
5 votes (15.62%)
2 votes (6.25%)
10 votes (31.25%)
3 votes (9.37%)
6 votes (18.75%)
5 votes (15.62%)
10 votes (31.25%)
7 votes (21.87%)

32 members have voted

teliot
teliot
Joined: Oct 19, 2009
  • Threads: 40
  • Posts: 2221
July 9th, 2021 at 6:31:10 AM permalink
Quote: GM

The denominators seem to be related to the sequence https://oeis.org/A079484.

Your link does not work (for me). It takes me to OEIS 404
Poetry website: www.totallydisconnected.com
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 105
  • Posts: 4925
July 9th, 2021 at 6:51:32 AM permalink
Quote: teliot

Your link does not work (for me). It takes me to OEIS 404


Try this one (the other one left a period in at the end of it)
teliot
teliot
Joined: Oct 19, 2009
  • Threads: 40
  • Posts: 2221
July 9th, 2021 at 8:13:52 AM permalink
Quote: ThatDonGuy

Try this one (the other one left a period in at the end of it)

Thanks. A fast growing sequence, but not really that fast. This is my favorite definition of this sequence from OEIS: "a(n) is the number of rooted, binary, leaf-labeled topologies with 2n+2 leaves that have n+1 cherry nodes."

I am a fan of big integers and fast growing integer sequences.
Poetry website: www.totallydisconnected.com
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 105
  • Posts: 4925
July 9th, 2021 at 9:58:21 AM permalink
Quote: Gialmere

How does this result change if two cards must first be selected, then turned over simultaneously?



The strategy is to always choose two unrevealed cards.

If there are N pairs initially, the expected number of turns is N (4N - 3) / (2N - 1).

charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 34
  • Posts: 2424
July 9th, 2021 at 4:15:56 PM permalink
Sorry I've only looked at two pairs.
Quote: ThatDonGuy


The strategy is to always choose two unrevealed cards.

If there are N pairs initially, the expected number of turns is N (4N - 3) / (2N - 1).

Taking the simple two pairs...let's assume the cards are AABB shuffled in boxes 1 thru 4. For argument' sake assume A is in Box 1. Then there are three scenarios, the other A is in Box 2, 3 or 4.

The basic method is to pick boxes 1 and 2. If both are A, then next turn is 3 and 4, for a total of two turns (AABB). If boxes 1 and 2 are A and B, then then next turn is to open box 3 (which will determine the order: ABAB or ABBA) and then the box which matches it, for a total of three turns.

So the average is (2 + 3 + 3)/3.


If you have to choose at the same time, with AABB you've done it in two moves. However with AB??, there is no point going for boxes 3 and 4 as you know they're AB or BA. So your second turn is boxes 1 and 3.

So with AABB it takes two turns; with ABAB it takes three turns (as your second turn is correct, and your third turn finds the two Bs); with ABBA it takes four turns.

So the average is (2+3+4)/3.


In your method if you miss on the first turn the second turn determines the order but you then need two further turns to find them. Your average is (2+4+4)/3.

In essence it's best to pick Boxes 1 and 2, 3 and 4, etc. But towards the end there's no point picking the last two boxes if you know they're wrong.

I'm guessing you're along the right lines as you will sometimes know the last N are all different, you can get rid of all the other pairs, and so change tack.
GM
GM
Joined: Jun 16, 2021
  • Threads: 0
  • Posts: 26
July 9th, 2021 at 5:20:50 PM permalink
Quote: ThatDonGuy

Quote: Gialmere

In the game of Memory, there are many different cards, each having one matching card to make its pair. To start the game, all the cards are spread out face down. On each turn, a player chooses a card and turns it over, then chooses a second card and turns it over. If the cards match, they are removed from the play area. If the cards do not match, they are returned to their face-down positions.

Assuming you have perfect memory (you can remember where all previously seen cards are), what is the expected number of turns needed to clear the play area for N pairs?


I have a feeling I'm going to regret this the minute I post it, but my numbers appear to be correct for 1 and 2 pairs...


E(n) is the expected number of turns starting with n pairs

E(1) = 1
E(2) = 8 / 3
E(3) = 199 / 45
E(4) = 9,556 / 1,575
E(5) = 786,227 / 99,225
E(6) = 94,036,576 / 9,823,275
E(7) = 3,219,603,572 / 280,945,665
E(8) = 17,964,806,816,248 / 1,369,610,116,875
E(9) = 5,244,142,302,537,988 / 349,250,579,803,125
E(10) = 1,197,405,952,584,220,562 / 71,786,869,175,896,875
E(11) = 23,420,230,525,515,820,899,299 / 1,260,290,275,252,045,537,500
E(12) = 1,849,433,417,098,530,134,834,771 / 91,308,030,442,010,699,191,875
E(13) = 116,341,686,404,284,568,353,640,366,753 / 5,250,211,750,415,615,203,532,812,500
E(14) = 464,625,053,499,588,757,386,024,329,118,739 / 19,491,411,123,417,971,443,115,566,406,250
E(15) = 1,571,462,235,083,358,151,475,317,163,097,678,737 / 61,047,099,638,545,086,559,837,953,984,375,000
E(16) = 2,445,858,396,189,803,074,022,490,793,281,058,154,971 / 89,182,181,684,459,553,328,103,271,026,923,828,125
E(17) = 856,246,260,751,723,619,649,577,491,266,529,944,091,817 / 29,194,678,996,224,679,377,487,886,803,373,784,375,000
E(18) = 65,369,036,717,836,848,555,054,164,570,348,117,457,561,106,219 / 2,107,490,890,039,969,042,562,406,828,618,545,059,570,312,500
E(19) = 1,437,505,462,224,141,765,319,683,046,425,447,630,110,336,927,272,279 / 43,667,211,241,628,158,561,893,069,488,976,253,634,296,875,000,000
E(20) = 10,310,653,070,695,057,740,633,755,272,380,500,522,403,004,373,859,041 / 297,886,640,425,022,346,407,619,267,973,881,111,763,886,718,750,000
E(21) = 187,624,995,670,444,822,761,102,760,795,505,677,506,365,650,106,369,786,860,009 / 5,138,548,121,971,320,575,799,589,263,980,664,864,500,387,065,078,125,000,000
E(22) = 50,592,299,927,532,945,252,436,026,478,265,788,089,433,539,553,647,978,381,421,123 / 1,324,045,741,859,025,579,442,760,319,812,002,545,893,611,273,222,476,562,500,000
E(23) = 133,589,616,167,475,641,370,900,261,774,634,214,899,298,766,597,156,639,802,988,694,899,579 / 3,330,637,063,646,378,845,088,263,584,487,092,404,195,379,157,791,139,792,968,750,000,000
E(24) = 128,853,864,436,997,375,220,430,317,002,564,689,920,778,943,592,415,883,972,086,015,579,536,013 / 3,081,880,107,955,289,925,095,733,898,020,712,690,257,036,776,943,614,039,681,396,484,375,000
E(25) = 410,512,353,054,960,488,444,975,685,589,029,270,251,940,073,462,813,937,125,465,066,511,797,934,447 / 9,392,272,935,318,058,306,460,177,664,789,018,295,612,813,554,323,317,229,142,714,843,750,000,000
E(26) = 232,892,409,664,096,187,950,738,679,941,658,818,172,913,536,412,245,920,476,876,384,899,053,693,789,540,201 / 5,128,476,879,281,122,354,163,910,500,571,244,843,480,908,004,287,492,391,604,640,300,205,078,125,000,000


I agree, but I don't have a formula either.

I have calculated E(n) numerically for n up to 5000 to try to see the asymptotic behaviour of E(n). It looks like E(n)/n may converge to a value around 1.81. (E(n)+2)/n is almost constant. Can anyone think of a good constant which is about 1.81?
Last edited by: GM on Jul 9, 2021
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 34
  • Posts: 2424
July 10th, 2021 at 2:07:19 AM permalink
Quote: GM

...I have calculated E(n) numerically for n up to 5000 to try to see the asymptotic behaviour of E(n). It looks like E(n)/n may converge to a value around 1.81. (E(n)+2)/n is almost constant. Can anyone think of a good constant which is about 1.81?

Try this idea.

As N gets large you look at pairs {1,2}, {3,4}...{2n-1,2n} (for large N it doesn't matter that you look at the last pairing, but this may be why you have the +2.).
At that stage you've used up N goes. Some of those will, by luck, have been pairs, but the rest you just match them up.
So the total number if (first run) N + (second run) N-pN (where p is the expected ratio of lucky matches) = 2N - pN = (2-p)/N.

So (E(n)/n) = (2-p).

I don't know the formula for having a random order of 1 to N and seeing how many are in the correct position, but if in this puzzle you consider N pairs (1st,2nd), (3rd,4th) and put the pairs in some order (say based on the value of the first entry and where they were in the first place). The rearrangement doesn't change the number of correct pairings but now can be considered as whether the second entry matches up with the reordered number.

Someone will know the formula for this, but my guess is p=1/2e as 1.816... is about 2 - 1/2e.
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 24
  • Posts: 1047
July 27th, 2021 at 9:12:03 PM permalink
If there was a “Fire-Repeater” bet, meaning you must hit all ten repeater bets before rolling a seven to win, what would be the probability of winning?
It’s all about making that GTA
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 105
  • Posts: 4925
July 28th, 2021 at 10:37:25 AM permalink
Quote: Ace2

If there was a “Fire-Repeater” bet, meaning you must hit all ten repeater bets before rolling a seven to win, what would be the probability of winning?


Assuming the bet is "roll each number from 2-6 and 8-12 N times before rolling a 7", the probability of winning for various values of N are:

2: 1 / 7350
3: 1 / 223,592
4: 1 / 6,122,965

Yes, this was done by number-crunching a Markov chain. I'll see if I can figure out the calculus-based method this time...
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 24
  • Posts: 1047
July 28th, 2021 at 12:05:07 PM permalink
I’ve never played repeater, but I’m asking what is the chance of rolling (at least) two 2s, three 3s, four 4s etc before rolling a 7.
It’s all about making that GTA

  • Jump to: