Shuffle a standard deck of cards. Deal from the top,
one card at a time, until the first ace appears. How
many cards must turn, on average, before that ace?
(if an ace is the top card, the count is zero)

An exact solution is desired, not an approximation to
the nearest integer.

Computers disallowed -

--
Rich

On 8/28/2021 6:18 PM, RichD wrote:
> Shuffle a standard deck of cards. Deal from the top,
> one card at a time, until the first ace appears. How
> many cards must turn, on average, before that ace?
> (if an ace is the top card, the count is zero)
>
> An exact solution is desired, not an approximation to
> the nearest integer.
>
> Computers disallowed -
>
> --
> Rich
>

52 cards, 4 aces

first card is 4/52, second is 4/51, third is 4/50

so it should be 4*Sum(1/52+1/51+1/51...) = 1/2

or roughly(skipping the summation, assumeing all are .02)

(1/2)/4 = k*.02 or

k* (2/100) = 1/8

or k = 100/2*(1/8) =100/16

or 6.25 cards

On Sat, 28 Aug 2021 16:18:24 -0700 (PDT), RichD
<r_delaney2001@yahoo.com> wrote:

>Shuffle a standard deck of cards. Deal from the top,
>one card at a time, until the first ace appears. How
>many cards must turn, on average, before that ace?
>(if an ace is the top card, the count is zero)
>
>An exact solution is desired, not an approximation to
>the nearest integer.
>
>Computers disallowed -

I assume no jokers in the deck.

The probability of an ace on the first card is 4/52 = ~.077

The probability of drawing the first ace on the second deal is
(48/52)*(4/51) = ~.072
The probability of drawing an ace on either the first or second deal
is the sum or ~.149

The probability of drawing the first ace on the third deal is
(48/52)*(47/51)*(4/50) = ~.068
The probability of drawing an ace on any of the first three deals is
the sum or ~.217

For any deal, the last term in the above product is always
4/m where m is 52 - deal# + 1
Similarly, the other terms in the product always evaluate to
48Cn / 52Cn where n is deal# - 1
and xCy is the standard combinatorial expression for choosing y items
from x possibilities ignoring order.

Continuing on produces the following table (best viewed monospaced)

deal prob of first ace cumulative probability
1 0.076923077 0.076923077
2 0.07239819 0.149321267
3 0.068054299 0.217375566
4 0.063887709 0.281263275
5 0.059894727 0.341158002
6 0.056071659 0.397229661
7 0.052414812 0.449644473
8 0.048920491 0.498564964
9 0.045585003 0.544149968
10 0.042404654 0.586554622
11 0.03937575 0.625930372
12 0.036494598 0.66242497

So the average number of deals before finding an ace is 7 and the ace
will, on average, turn up on the eighth.

This appears analogous to the well known puzzle: "On average, how many
people need to be in a room before two share a birthday (ignoring
year)?" 23 seems as intuitively absurdly low as 8 does for your
puzzle.

--
Remove del for email

On Saturday, August 28, 2021 at 4:18:31 PM UTC-7, RichD wrote:
> How many cards must turn, on average, before that ace?
> (if an ace is the top card, the count is zero)

If the deck is 1,1,1,1 then the average is 0/5
If the deck is 1,1,1,1,2,2,2,2 then the average is 4/5
If the deck is 1,1,1,1,2,2,2,2,3,3,3,3 then the average is 8/5
If the deck is 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 then the average is 12/5
and I am then guessing that the ordering persists and thus
If the deck is 1,1,1,1,2,2,2,2....12,12,12,12,13,13,13,13 then the average is 48/5=9.6

RichD formulated on Saturday :
> Shuffle a standard deck of cards. Deal from the top,
> one card at a time, until the first ace appears. How
> many cards must turn, on average, before that ace?
> (if an ace is the top card, the count is zero)
>
> An exact solution is desired, not an approximation to
> the nearest integer.
>
> Computers disallowed -

Six and a half.

Barry Schwarz <schwarzb@delq.com> wrote:
> On Sat, 28 Aug 2021 16:18:24 -0700 (PDT), RichD
> <r_delaney2001@yahoo.com> wrote:
>
>>Shuffle a standard deck of cards. Deal from the top,
>>one card at a time, until the first ace appears. How
>>many cards must turn, on average, before that ace?
>>(if an ace is the top card, the count is zero)

About 9.599823, if we overlook the next two requirements and if I
correctly subtracted 1. (Ie, this answer is not exact; used a
computer to sum up the total; and might be off by 1.)

>>An exact solution is desired, not an approximation to
>>the nearest integer.

>>Computers disallowed -

<snip Barry's assumptions & first two examples>
> The probability of drawing the first ace on the third deal is
> (48/52)*(47/51)*(4/50) = ~.068
> The probability of drawing an ace on any of the first three deals is
> the sum or ~.217

I agree with the probabilities you show, and the remark about sum of
probabilities, but of course a further calculation is needed to get
the expected value (the average). In general, an expected value is
the sum (over all cases) of the value of a case times its probability.

In other words, if we call the first and second values in row i of
your table d_i and p_i, and let E(52) = E(deal number for first ace
given 4 aces among 52 cards), then E(52) = sum{i=1 to 52}( d_i*p_i).

The answer to the question is E(52)-1.

Generally, if there are g good cards (aces) and c cards total, we
can write E(c) = g/c + (1-g/c)*(1+E(c-1)), a recursive equation that
can be solved analytically.
> For any deal, the last term in the above product is always
> 4/m where m is 52 - deal# + 1
> Similarly, the other terms in the product always evaluate to
> 48Cn / 52Cn where n is deal# - 1
> and xCy is the standard combinatorial expression for choosing y items
> from x possibilities ignoring order.
>
> Continuing on produces the following table (best viewed monospaced)
>
> deal prob of first ace cumulative probability
> 1 0.076923077 0.076923077
> 2 0.07239819 0.149321267
> 3 0.068054299 0.217375566
> 4 0.063887709 0.281263275
> 5 0.059894727 0.341158002
> 6 0.056071659 0.397229661
> 7 0.052414812 0.449644473
> 8 0.048920491 0.498564964
> 9 0.045585003 0.544149968
> 10 0.042404654 0.586554622
> 11 0.03937575 0.625930372
> 12 0.036494598 0.66242497
>
> So the average number of deals before finding an ace is 7 and the ace
> will, on average, turn up on the eighth.
>
> This appears analogous to the well known puzzle: "On average, how many
> people need to be in a room before two share a birthday (ignoring
> year)?" 23 seems as intuitively absurdly low as 8 does for your
> puzzle.
>
>
>
>

James Waldby <j-waldby@no.no> wrote:
> Barry Schwarz <schwarzb@delq.com> wrote:
>> On Sat, 28 Aug 2021 16:18:24 -0700 (PDT), RichD
>> <r_delaney2001@yahoo.com> wrote:
>>
>>>Shuffle a standard deck of cards. Deal from the top,
>>>one card at a time, until the first ace appears. How
>>>many cards must turn, on average, before that ace?
>>>(if an ace is the top card, the count is zero)
>
> About 9.599823, if we overlook the next two requirements and if I
> correctly subtracted 1. (Ie, this answer is not exact; used a
> computer to sum up the total; and might be off by 1.)

In my program I ran the summation only to 48 instead of 52, thus was
one short step away from a probably exact answer, 9.6

>>>An exact solution is desired, not an approximation to
>>>the nearest integer.
>
>>>Computers disallowed -

On 8/29/2021 5:53 PM, James Waldby wrote:
> James Waldby <j-waldby@no.no> wrote:
>> Barry Schwarz <schwarzb@delq.com> wrote:
>>> On Sat, 28 Aug 2021 16:18:24 -0700 (PDT), RichD
>>> <r_delaney2001@yahoo.com> wrote:
>>>
>>>> Shuffle a standard deck of cards. Deal from the top,
>>>> one card at a time, until the first ace appears. How
>>>> many cards must turn, on average, before that ace?
>>>> (if an ace is the top card, the count is zero)
>>
>> About 9.599823, if we overlook the next two requirements and if I
>> correctly subtracted 1. (Ie, this answer is not exact; used a
>> computer to sum up the total; and might be off by 1.)
>
> In my program I ran the summation only to 48 instead of 52, thus was
> one short step away from a probably exact answer, 9.6
>
>>>> An exact solution is desired, not an approximation to
>>>> the nearest integer.
>>
>>>> Computers disallowed -

but that is not an exact answer....
it has a variance

you can calculate the mean to great precision, but if the variance is large, using the mean is error.

take daily temperatures, from 60 to 81 in one day, 24 hours say you took reading every min, and averaged them and got 70.9565217391304, and the Standard
Deviation is is 8.52524732176335

If you used 70.9565217391304, that temperature only happened twice per day, the rest of the time it is wrong.

here it is per hour

60
60
60
61
62
65
68
70
72
75
78
80
80
83
85
85
80
76
70
68
67
64
63

Column 1
Mean 70.9565217391304
Standard Error 1.77763694998913
Mode 60
Median 70
First Quartile 63.5
Third Quartile 79
Variance 72.6798418972332
Standard Deviation 8.52524732176335
Kurtosis -1.31090489291319
Skewness 0.259643417326634
Range 25
Minimum 60
Maximum 85
Sum 1632
Count 23

Same with your case of aces and card deck.

One always calculates the mean AND the Standard Deviation (or variance).

Serg io <invalid@invalid.com> wrote:
> On 8/29/2021 5:53 PM, James Waldby wrote:
>> James Waldby <j-waldby@no.no> wrote:
>>> Barry Schwarz <schwarzb@delq.com> wrote:
>>>> On Sat, 28 Aug 2021 16:18:24 -0700 (PDT), RichD
>>>> <r_delaney2001@yahoo.com> wrote:
>>>>
>>>>> Shuffle a standard deck of cards. Deal from the top,
>>>>> one card at a time, until the first ace appears. How
>>>>> many cards must turn, on average, before that ace?
>>>>> (if an ace is the top card, the count is zero)
>>>...
>> ... probably exact answer, 9.6
....
> but that is not an exact answer....
> it has a variance

The question asks for the mean of a certain distribution, which in
this case is a specific fixed number. The mean of this distribution
does not change -- it's a fixed number.

If you take random samples from this distribution, yes, sample values
will vary in accord with the variance of the distribution. If you
take j sets of k samples each and compute averages m_j for each j,
yes, those m_j will vary, in accord with the variance-of-the-mean of
the distribution. Random-sample averages are sample statistics, and
sample statistics will vary randomly depending on the random nature of
the distribution. But the mean and variance of the distribution
itself do not vary.

In this case, the mean of the distribution is 9.6, and the standard
deviation of the distribution is ~ 8.22.
> you can calculate the mean to great precision, but if the variance is large, using the mean is error.

"Using the mean" is not an error, it's what the question asks for.

>
[snip not-relevant example of computing temperature sample statistics]

>
> Same with your case of aces and card deck.
>
> One always calculates the mean AND the Standard Deviation (or variance).

That is demonstrably false. Demonstration: This `daily puzzle`
doesn't ask for standard deviation or variance, so they don't need to
be calculated.

(As it happens, the standard deviation of this distribution is about
8.22, and its mean is 9.6.)

daily puzzle: where's the first ace? ??????????????????????????????

FromTheRafters wrote :
> RichD formulated on Saturday :
>> Shuffle a standard deck of cards. Deal from the top, one card at a time,
>> until the first ace appears. How many cards must turn, on average, before
>> that ace? (if an ace is the top card, the count is zero)
>>
>> An exact solution is desired, not an approximation to the nearest integer.
>>
>> Computers disallowed -
>
> Six and a half.

I'll change that to five and a half since you want to call the first
card dealt number zero.

On 29/08/2021 23:53, James Waldby wrote:
> James Waldby <j-waldby@no.no> wrote:
>> Barry Schwarz <schwarzb@delq.com> wrote:
>>> On Sat, 28 Aug 2021 16:18:24 -0700 (PDT), RichD
>>> <r_delaney2001@yahoo.com> wrote:
>>>
>>>> Shuffle a standard deck of cards. Deal from the top,
>>>> one card at a time, until the first ace appears. How
>>>> many cards must turn, on average, before that ace?
>>>> (if an ace is the top card, the count is zero)
>>
>> About 9.599823, if we overlook the next two requirements and if I
>> correctly subtracted 1. (Ie, this answer is not exact; used a
>> computer to sum up the total; and might be off by 1.)
>
> In my program I ran the summation only to 48 instead of 52, thus was
> one short step away from a probably exact answer, 9.6
>

OK, and I get the same by cheating with a computer program.

So this is the same as bwr's prediction, and bwr's hypothesis that with
4 "success" cards (the aces) and 4n "fail" cards (all the others) the
expectation is 4n/5 seems to be correct!

But if I write the calculation for the answer as a formula (a sum of the
contributions for each "first ace" position) I don't see how that
simplifies to 4n/5.

And more than that - for such a simple answer, there's got to be some
simple way of viewing the problem that makes the answer obvious!
(Surely...)

Well, I suppose 4n is the number of fail cards, and 5 is, um, one more
than the number of success cards, but why divide fail cards by one more
than the number of success cards? (I'm still thinking about that...)

Regards,
Mike.

>>>> An exact solution is desired, not an approximation to
>>>> the nearest integer.
>>
>>>> Computers disallowed -

On 8/30/2021 1:12 AM, James Waldby wrote:
> Serg io <invalid@invalid.com> wrote:
>> On 8/29/2021 5:53 PM, James Waldby wrote:
>>> James Waldby <j-waldby@no.no> wrote:
>>>> Barry Schwarz <schwarzb@delq.com> wrote:
>>>>> On Sat, 28 Aug 2021 16:18:24 -0700 (PDT), RichD
>>>>> <r_delaney2001@yahoo.com> wrote:
>>>>>
>>>>>> Shuffle a standard deck of cards. Deal from the top,
>>>>>> one card at a time, until the first ace appears. How
>>>>>> many cards must turn, on average, before that ace?
>>>>>> (if an ace is the top card, the count is zero)
>>>> ...
>>> ... probably exact answer, 9.6
> ...
>> but that is not an exact answer....
>> it has a variance
>
> The question asks for the mean of a certain distribution, which in
> this case is a specific fixed number. The mean of this distribution
> does not change -- it's a fixed number.

which is my point, you can calculate the mean to great precision, which does not apply in real life.

what does 9.6 cards mean ? you snip a card? 40% off the last one ?

How many trials do you go through to establish it is 9.6 cards? 1000 ? Confidence intervals of 95% ?

> But the mean and variance of the distribution
> itself do not vary.
>
> In this case, the mean of the distribution is 9.6, and the standard
> deviation of the distribution is ~ 8.22.
>
>> you can calculate the mean to great precision, but if the variance is large, using the mean is error.
>
> "Using the mean" is not an error, it's what the question asks for.

9.6 is meaningless. who has 0.6 of a card ?

So you prefer to not understand the entire problem ? Just answer the mail ?

that is a disservice and irresponsible in many cases.

>

>> Same with your case of aces and card deck.
>>
>> One always calculates the mean AND the Standard Deviation (or variance).
>
> That is demonstrably false. Demonstration: This `daily puzzle`
> doesn't ask for standard deviation or variance, so they don't need to
> be calculated.

so you like the race to the bottom...
I like to expand the problems

>
> (As it happens, the standard deviation of this distribution is about
> 8.22, and its mean is 9.6.)

which means.... only 67% of the time the # of cards dealt to hit an ace, is within 6 to 12 ...?

you hang too much weight on the mean.

FromTheRafters used his keyboard to write :
> FromTheRafters wrote :
>> RichD formulated on Saturday :
>>> Shuffle a standard deck of cards. Deal from the top, one card at a time,
>>> until the first ace appears. How many cards must turn, on average, before
>>> that ace? (if an ace is the top card, the count is zero)
>>>
>>> An exact solution is desired, not an approximation to the nearest integer.
>>>
>>> Computers disallowed -
>>
>> Six and a half.
>
> I'll change that to five and a half since you want to call the first card
> dealt number zero.

Special today, limited time offer, one half off - so now it is five
even.

Five, going once, going twice...

On August 28, Barry Schwarz wrote:
>> Shuffle a standard deck of cards. Deal from the top,
>> one card at a time, until the first ace appears. How
>> many cards must turn, on average, before that ace?
>> (if an ace is the top card, the count is zero)
>
> The probability of an ace on the first card is 4/52 = ~.077
> The probability of drawing the first ace on the second deal is
> (48/52)*(4/51) = ~.072
> The probability of drawing an ace on either the first or second deal
> is the sum or ~.149
> Continuing on produces the following table

[snip mind numbing combinatorial gymnastics]

oh jeez -
Look, any puzzle worth its salt is the "aha!" type. If it requires hard labor,
it won't get posted!

There is an elegant, non-obvious solution to this problem.
Obviously non-obvious, since nobody recognized it. Though admittedly,
somebody solved it -

"It is unworthy of good men to spend time like slaves in the labor of calculation."

--
Rich

On August 28, 2021, bwr fml wrote:
>> How many cards must turn, on average, before that ace?
>> (if an ace is the top card, the count is zero)
>
> If the deck is 1,1,1,1 then the average is 0/5
> If the deck is 1,1,1,1,2,2,2,2 then the average is 4/5
> If the deck is 1,1,1,1,2,2,2,2,3,3,3,3 then the average is 8/5
> If the deck is 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 then the average is 12/5
> and I am then guessing that the ordering persists and thus
> If the deck is 1,1,1,1,2,2,2,2....12,12,12,12,13,13,13,13 then the average is 48/5=9.6

I have no idea what you're talking about.
But by some infernal miracle, you got the right answer.
I might ask you to explain it plain English, but you'd probly respond
"Dude, I provided the proof!"
So I won't bother -

--
Rich

On Monday, August 30, 2021 at 4:58:48 PM UTC-7, RichD wrote:
> On August 28, 2021, bwr fml wrote:
> >> How many cards must turn, on average, before that ace?
> >> (if an ace is the top card, the count is zero)
> >
> > If the deck is 1,1,1,1 then the average is 0/5
> > If the deck is 1,1,1,1,2,2,2,2 then the average is 4/5
> > If the deck is 1,1,1,1,2,2,2,2,3,3,3,3 then the average is 8/5
> > If the deck is 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 then the average is 12/5
> > and I am then guessing that the ordering persists and thus
> > If the deck is 1,1,1,1,2,2,2,2....12,12,12,12,13,13,13,13 then the average is 48/5=9.6
> I have no idea what you're talking about.
> But by some infernal miracle, you got the right answer.
> I might ask you to explain it plain English, but you'd probly respond
> "Dude, I provided the proof!"
> So I won't bother -

I'll try to politely try to explain a little about this in sort-of plain English.
I would never be rude enough to claim that what I posted was a proof.
I intentionally didn't post all the details because I don't want to spoil the puzzle for anyone else.

I read the first two responses and they didn't seem headed towards the kind of result I would immediately accept.
So I thought "I need to see an invariant in this, an invariant has to be hiding inside this somewhere."
To do that I need to start with a base case and I need to draw myself a series of diagrams.
The 1,1,1,1 case is too simple and might just be a distraction, but the average for that has to be zero, check that later.

So I started working on the diagram for the 1,1,1,1,2,2,2,2 case.
Because we don't care about the order of the 1's or the order of the 2's this will be much smaller than 8 factorial, very good.
We also might not care about the tail of the sequence, just the head might be enough and that will become essential.
Combinatorics, or just a bit of thinking and a couple of divisions says there are only 70 distinct permutations, even with the tails.
That is within reach of drawing a diagram, even better without the tails.
And I counted all the multiplicities and path lengths in that diagram and I got 4/5.

Then I started thinking about the diagram for the 1,1,1,1,2,2,2,2,3,3,3,3 case.
Even without the ordering that is 34650 cases, too many for any diagram.
We only care about is it a 1 or is it not a 1, but be careful with permutations when you start thinking that.
Ignoring the tails brings that down to a far more reasonable number, just count how many different tails there are.
I needed to find that invariant. That means I needed to find the right way to diagram this.
After a few dead ends and tossing out the previous diagram and starting over a couple of times...
I thought I found the structure for the diagram that showed an invariant.
When I totaled up all the levels I got 8/5 and thought that must mean I'd made a mistake, it didn't feel right.
But I checked it twice and still got the same number, so I will hope that is right until proven wrong.

The 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 case would be out of the question, even ignoring the repetitions,
if you didn't already have a diagram to fit it into.
There are just more layers and lots more tails and more opportunities to make little mistakes.
But the diagram forces the path. And the path fits the invariant. And I got 12/5.

This method is more than just a brute force counting argument.
But I suppose that would work too, just perhaps not giving you anything more than a single number each time.

I STILL was not certain this was right. I did not expect the invariant to scale linearly. But it did match the 1.1.1.1 case.
There is no way I could, even with the diagram and the invariant, scale this up to 5,5,5,5.
I gambled and posted it, with the cautions that I was still just guessing this was correct, like others I suppose.

But the structure of the diagram, that represents the invariant, those diagrams hint this will not change with n.

And it looks like someone did Monte Carlo and agreed with my conjecture for 13.13.13.13.

I've been mumbling about the post which said he couldn't simplify his sum of products down to 4n/5.
I've tried that a couple of different ways and am still not happy with that yet, but it may work out.
It has to work. I just have to find some way to translate the diagrams into the sum of products.

So, what I've just written is NOT a proof.
A proof would require that I show how the diagram is constructed and how the structure is invariant.
I didn't want to spoil this for anyone else. Why ruin fun for anyone else?
But I think there are enough hints in this that if you have the right background that you might duplicate this.

I hope this was polite. I hope this might be just enough of a hint, and not too much of a hint.

Does any of this help at all?

Slightly different subject: average versus average and variance.
It is a puzzle. It is a challenge. It is nothing more than an exercise for fun.
It is perhaps meant to get you to try to find any way to correctly solve a problem at the edge of your ability.
Those are the best kind.
It is meant to be a diversion from the usual posts made here, I'll not say a word more about that to avoid attracting unwanted attention.

On 31/08/2021 02:54, bwr fml wrote:
> On Monday, August 30, 2021 at 4:58:48 PM UTC-7, RichD wrote:
>> On August 28, 2021, bwr fml wrote:
>>>> How many cards must turn, on average, before that ace?
>>>> (if an ace is the top card, the count is zero)
>>>
>>> If the deck is 1,1,1,1 then the average is 0/5
>>> If the deck is 1,1,1,1,2,2,2,2 then the average is 4/5
>>> If the deck is 1,1,1,1,2,2,2,2,3,3,3,3 then the average is 8/5
>>> If the deck is 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 then the average is 12/5
>>> and I am then guessing that the ordering persists and thus
>>> If the deck is 1,1,1,1,2,2,2,2....12,12,12,12,13,13,13,13 then the average is 48/5=9.6
>> I have no idea what you're talking about.
>> But by some infernal miracle, you got the right answer.
>> I might ask you to explain it plain English, but you'd probly respond
>> "Dude, I provided the proof!"
>> So I won't bother -
>
> I'll try to politely try to explain a little about this in sort-of plain English.
> I would never be rude enough to claim that what I posted was a proof.
> I intentionally didn't post all the details because I don't want to spoil the puzzle for anyone else.
>
> I read the first two responses and they didn't seem headed towards the kind of result I would immediately accept.
> So I thought "I need to see an invariant in this, an invariant has to be hiding inside this somewhere."
> To do that I need to start with a base case and I need to draw myself a series of diagrams.
> The 1,1,1,1 case is too simple and might just be a distraction, but the average for that has to be zero, check that later.
>
> So I started working on the diagram for the 1,1,1,1,2,2,2,2 case.
> Because we don't care about the order of the 1's or the order of the 2's this will be much smaller than 8 factorial, very good.
> We also might not care about the tail of the sequence, just the head might be enough and that will become essential.
> Combinatorics, or just a bit of thinking and a couple of divisions says there are only 70 distinct permutations, even with the tails.
> That is within reach of drawing a diagram, even better without the tails.
> And I counted all the multiplicities and path lengths in that diagram and I got 4/5.
>
> Then I started thinking about the diagram for the 1,1,1,1,2,2,2,2,3,3,3,3 case.
> Even without the ordering that is 34650 cases, too many for any diagram.
> We only care about is it a 1 or is it not a 1, but be careful with permutations when you start thinking that.
> Ignoring the tails brings that down to a far more reasonable number, just count how many different tails there are.
> I needed to find that invariant. That means I needed to find the right way to diagram this.
> After a few dead ends and tossing out the previous diagram and starting over a couple of times...
> I thought I found the structure for the diagram that showed an invariant.
> When I totaled up all the levels I got 8/5 and thought that must mean I'd made a mistake, it didn't feel right.
> But I checked it twice and still got the same number, so I will hope that is right until proven wrong.
>
> The 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 case would be out of the question, even ignoring the repetitions,
> if you didn't already have a diagram to fit it into.
> There are just more layers and lots more tails and more opportunities to make little mistakes.
> But the diagram forces the path. And the path fits the invariant. And I got 12/5.
>
> This method is more than just a brute force counting argument.
> But I suppose that would work too, just perhaps not giving you anything more than a single number each time.
>
> I STILL was not certain this was right. I did not expect the invariant to scale linearly. But it did match the 1.1.1.1 case.
> There is no way I could, even with the diagram and the invariant, scale this up to 5,5,5,5.
> I gambled and posted it, with the cautions that I was still just guessing this was correct, like others I suppose.
>
> But the structure of the diagram, that represents the invariant, those diagrams hint this will not change with n.
>
> And it looks like someone did Monte Carlo and agreed with my conjecture for 13.13.13.13.

The people getting the answer 48/5 for 13.13.13.13 just evaluated the
answer on a computer, so it's an exact answer, not a Monte Carlo. It's
easy enough to write down an expression for the correct answer to the
problem, but turning that expression into 48/5 by actually evaluating
the sum itself is going to be hugely error prone, and besides, time
consuming in a not at all interesting way. (This sounds like the
calculations you did with your diagrams guiding you, but I'm not sure...)

Someone else actually posted the expression to compute I think, but the
point is that the expression is obvious enough, but not what RichD hoped
for - he intended solvers to find a simplified way of looking at the
problem which would lead to a simple (and obvious) answer.

Anyway, I just wrote a program with a couple of loops to calculate the
sum, nothing clever, and not the intention behind the problem. But
still, it can be very useful to spot a pattern in the answers [I think
that's what your "invariant" means] because that pattern might lead us
to look for a particular simplification for the problem that is likely
to lead to the sort of pattern we see.

>
> I've been mumbling about the post which said he couldn't simplify his sum of products down to 4n/5.
> I've tried that a couple of different ways and am still not happy with that yet, but it may work out.

That was me - I'm quite sure there is a way to simplify the sum of
products into 4n/5, but I still can't see the right route. 40 years ago
I was pretty good at those sorts of algebraic manipulations, but to say
I'm a bit rusty these days would be a total understatement! :)

I would still like to see how to do the algebraic manipulations to get
the answer, even though I've now seen what RichD intended. Knowing the
right answer was likely to be 4n/5 did indeed send me in the right
direction, but I didn't see the final solution until RichD posted in
another thread ["dropping points on a line"] giving a HUGE hint for the
bit I was missing.

I posted what I guess is RichD's intended solution on that thread, so if
you still want to work on the problem, DON'T READ MY POST ON THAT THREAD
- there's no spoiler space or anything. If it had been posted to
rec.puzzles I would automatically have thought to add spoiler space out
of habit, but being on sci.math that didn't occur to me I'm afraid. (Too
late now...)

Mike.

On Tue, 31 Aug 2021 15:47:34 +0100, Mike Terry
<news.dead.person.stones@darjeeling.plus.com> wrote, among other
things:

>I'm quite sure there is a way to simplify the sum of
>products into 4n/5, but I still can't see the right route.
>
>I would still like to see how to do the algebraic manipulations to get
>the answer, even though I've now seen what RichD intended.

For a non-cleverjust-plodding-along solution one might start by noting
that the specific identities of the aces and non-aces are irrelevant
for the problem, so one might as well assume that both the aces and
the non-aces are indistinguishable.

Then, writing the binomial coefficients p!/(q!(p-q)! as C(p,q), for a
deck of n cards including a aces, there are C(n,a) different
configurations and the answeris

1/C(n,a) * Sum(j = 0 .. n-a; j * C(n-j-1,a-1)) =

1/C(n,a) * Sum(k = 1 .. n-a; [Sum(j = k .. n-a; C(n-j-1,a-1)]).

Using the hockey-stick_identity twice results in (see
https://en.wikipedia.org/wiki/Hockey-stick_identity)

1/C(n,a) * Sum(k = 1 .. n-a; C(n-k,a)) = C(n,a+1)/C(n.a)= (n-a)/(a+1)

On 02/09/2021 14:28, Leon Aigret wrote:
> On Tue, 31 Aug 2021 15:47:34 +0100, Mike Terry
> <news.dead.person.stones@darjeeling.plus.com> wrote, among other
> things:
>
>> I'm quite sure there is a way to simplify the sum of
>> products into 4n/5, but I still can't see the right route.
>>
>> I would still like to see how to do the algebraic manipulations to get
>> the answer, even though I've now seen what RichD intended.
>
> For a non-cleverjust-plodding-along solution one might start by noting
> that the specific identities of the aces and non-aces are irrelevant
> for the problem, so one might as well assume that both the aces and
> the non-aces are indistinguishable.
>
> Then, writing the binomial coefficients p!/(q!(p-q)! as C(p,q), for a
> deck of n cards including a aces, there are C(n,a) different
> configurations and the answeris
>
> 1/C(n,a) * Sum(j = 0 .. n-a; j * C(n-j-1,a-1)) =
>
> 1/C(n,a) * Sum(k = 1 .. n-a; [Sum(j = k .. n-a; C(n-j-1,a-1)]).
>
> Using the hockey-stick_identity twice results in (see
> https://en.wikipedia.org/wiki/Hockey-stick_identity)
>
> 1/C(n,a) * Sum(k = 1 .. n-a; C(n-k,a)) = C(n,a+1)/C(n.a)= (n-a)/(a+1)
>

Thanks for that. It was the Hockey-stick identity I was unaware of (or
had forgotten), and couldn't recreate from scratch. (It's obvious
enough when looking at Pascal's triangle, and I could see the
combinatorial expressions in my formula but it didn't click.)

Mike.

In article <d66b1c5d-3cd8-460f-bf6d-430fe8118ed1n@googlegroups.com>,
RichD <r_delaney2001@yahoo.com> wrote:
>Shuffle a standard deck of cards. Deal from the top,
>one card at a time, until the first ace appears. How
>many cards must turn, on average, before that ace?
>(if an ace is the top card, the count is zero)
>
>An exact solution is desired, not an approximation to
>the nearest integer.
>
>Computers disallowed -

The four aces partition the remaining 48 cards into 5 partitions.
So the average partition length is 9.6.

But it's not immediately obvious (to me) that the average length of
the *first* partition is same as the overall average partition length.

Instead put the 48 other cards in a circle, and randomly insert the
four aces and a "start of deck" marker. Now it's clear that the
partition from the start of deck to the first ace has average length
9.6.

-- Richard