Month: February 2022

Curt Cutting

This challenge is about cutting cards. And therefore about probability and combinatorics.

You have a deck of cards. For convenience, we’ll just use A-9 to have a nice round 40 cards. You cut some number of cards. At least one quarter and less than 3/4. That’s a neat 20 possible number of cards. To keep things simple, make them all have a probability of 5%. Now, from this cutting you cut a number of single cards, shuffling in between cuts of course. Formally, that’s random selection with replacement. At some point, you will cut a card that you have seen previously. At this point, you stop. This cuts short the data you receive about the deck of cards; you haven’t seen half of them. Of course, one can always estimate the remaining number of cards. So say you cut 10 cards before a repetition (11 cards total), and that for some reason you cannot visually approximate how many cards are in the deck. The challenge is to determine the expected number of cards in the deck.

The expected number of cards, to put it simply, is the “best” guess for how many cards are in the deck given your information. “Best” means minimizing the average difference between the actual number and your guess.

Solution

Solution to Cantankerous Circle

We’re trying to determine the average distance from a random point in a circle to the centre, for various definitions of average. The simplest, the arithmetic mean distance, is ≈ .6667.

\iint_R \ln \operatorname f x\ \delta A

First, the geometric mean. The basic integral required to solve this is above. It’s not a very hard integral, especially for a circle. It’s equal to 2π times the integral from 0 to 1 of x2 ln x. That’s a relatively simple integration by parts, which many already know how to do–but for completion:

\int_0^1 x^2 \ln x\ \delta x \\[16pt] \int_0^1 \ln x \cdot x^2\ \delta x \implies \xcancel{\left[ {x^3\ln x\over 3}\right]}_0^1-\int_0^1 \frac{x^2}3 \delta x \\[16pt] = {\left[\frac{x^3}9\right]}_0^1 = -\frac19

Substituting, the geometric mean distance is e-2/9 ≈ .8007. Note that this is -2/9 not -1/9 because we multiplied the integral by 2π.

Second: the quadratic mean. Since we’re using the identity function, this is a rather easy one. The integral of x2 times x is 1/4 x4, from 0 to 1 that’s just 1/4. We take the square root of 1/8, not 1/4, for the same reason as with the geometric mean. Thus, the quadratic mean distance is ≈ .3536.

Third: the harmonic mean. We saved the best for last: the determinant of the transformation from cartesian to polar coordinates is x. 1/x times x is 1. It’s the easiest integral of all! The harmonic mean distance is .5.

And last, the extra easy cool-down problem, that’s not even really integration at all. This one is fairly obvious: the median distance is ≈ .7071.