Expected maximums and fun with Faulhaber’s formula

A recent Futility Closet post inspired this one. There, Greg Ross mentioned a 2020 paper by P Sullivan titled “Is the Last Banana Game Fair?” in Mathematics Teacher. (BTW, it’s behind a paywall and I haven’t seen that paper). I’m not going to define the last banana game, but instead look at a related question.

Let’s define things more generally. Let I_n=\{1,2,...,n\}, let X,Y be two independent, uniform random variables taken from I_n, and let Z=max(X,Y). The last banana game post above concerns the case n=6. Here, I’m interested in investigating the question: What is E(Z)?

Computing this isn’t hard. By definition of independent and max, we have
P(Z\leq z)=P(X\leq z)P(Y\leq z).
Since P(X\leq z)=P(Y\leq z)={\frac{z}{n}}, we have
P(Z\leq z)={\frac{z^2}{n^2}}.
The expected value of Z is defined as \sum kP(Z=k), but there’s a handy-dandy formula we can use instead:
E(Z)=\sum_{k=0}^{n-1} P(Z>k)=\sum_{k=0}^{n-1}[1-P(Z\leq k)].
Now we use the previous computation to get
E(Z)=n-{\frac{1}{n^2}}\sum_{k=1}^{n-1}k^2=n-{\frac{1}{n^2}}{\frac{(n-1)n}{6}}={\frac{2}{3}}n+{\frac{1}{2}}-{\frac{1}{6n}}.
This solves the problem as stated. But this method generalizes in a straightforward way to selecting m independent r.v.s in I_n, so let’s keep going.

First, let’s pause for some background and history. Notice how, in the last step above, we needed to know the formula for the sum of the squares of the first n consecutive positive integers? When we generalize this to selecting m integers, we need to know the formula for the sum of the m-th powers of the first n consecutive positive integers. This leads to the following topic.

Faulhaber polynomials are, for this post (apparently the terminology is not standardized) the sequence of polynomials F_m(n) of degree m+1 in the variable n that gives the value of the sum of the m-th powers of the first n consecutive positive integers:

\sum_{k=1}^{n} k^m=F_m(n).

(It is not immediately obvious that they exist for all integers m\geq 1 but they do and Faulhaber’s results establish this existence.) These polynomials were discovered by (German) mathematician Johann Faulhaber in the early 1600s, over 400 years ago. He computed them for “small” values of m and also discovered a sort of recursive formula relating F_{2\ell +1}(n) to F_{2\ell}(n). It was about 100 years later, in the early 1700s, that (Swiss) mathematician Jacob Bernoulli, who referenced Faulhaber, gave an explicit formula for these polynomials in terms of the now-famous Bernoulli numbers. Incidentally, Bernoulli numbers were discovered independently around the same time by (Japanese) mathematician Seki Takakazu. Concerning the Faulhaber polys, we have
F_1(n)={\frac{n(n+1)}{2}},
F_2(n)={\frac{n(n+1)(2n+1)}{6}},
and in general,
F_m(n)={\frac{n^{m+1}}{m+1}}+{\frac{n^m}{2}}+ lower order terms.

With this background aside, we return to the main topic of this post. Let I_n=\{1,2,...,n\}, let X_1,X_2,...,x_m be m independent, uniform random variables taken from I_n, and let Z=max(X_1,X_2,...,X_m). Again we ask: What is E(Z)? The above computation in the m=2 case generalizes to:

E(Z)=n-{\frac{1}{n^m}}\sum_{k=1}^{n-1}k^m=n-{\frac{1}{n^m}}F_m(n-1).

For m fixed and n “sufficiently large”, we have

E(Z)={\frac{m}{m+1}}n+O(1).

I find this to be an intuitively satisfying result. The max of a bunch of independently chosen integers taken from I_n should get closer and closer to n as (the fixed) m gets larger and larger.

Michael Reid’s Happy New Year Puzzles, 2018

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some New Year’s puzzles to help start out 2018.

1. Arrange the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 in the
expression a^b + c^d + e^f + g^h + i^j to make 2018.

2. (a) Express 2018 = p^q + r^s where p, q, r, s are primes.
(b) Express 2018 = p^q - r^s where p, q, r, s are primes.

3. (a) Is it possible to put the first 9 primes, 2, 3, 5, 7, 11, 13,
17, 19 and 23 into a 3×3 matrix that has determinant 2018?
(b) Is it possible to put the first 16 primes, 2, 3, 5, … , 53,
into a 4×4 matrix that has determinant 2018?

4. (a) Express 2018 = A / B using the fewest number of distinct
digits.
For example, the expression 7020622 / 3479 uses only seven
different digits. But it is possible to do better than this.
(b) Express 2018 = (A_1 \cdot A_2 \cdot ... \cdot A_m) / (B_1 \cdot B_2 \cdot ... \cdot B_n) using the fewest number of distinct digits.

Michael Reid’s Happy New Year Puzzle, 2017

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some interesting puzzles to start the New Year; hopefully they are not too easy!

1. Express 2017 as a quotient of palindromes.

2. (a) Are there two positive integers whose sum is 2017 and whose product
is a palindrome?
(b) Are there two positive integers whose difference is 2017 and whose
product is a palindrome?

3. Is there a positive integer n such that both 2017 + n and
2017 n are palindromes?

4. What is the smallest possible sum of the decimal digits of 2017 n ,
where n is …
(a) … a positive integer?
(b) … a prime number?
(c) … a palindrome?

5. Consider the following two operations on a positive integer:
(i) replace a string of consecutive digits by its square,
(ii) if a string of consecutive digits is a perfect cube,
replace the string by its cube root.

Neither the string being replaced, nor its replacement, may have
have “leading zeros”. For example, from 31416 , we may change it to
319616 , by squaring the 14 . From 71253 , we may change it to
753 by taking the cube root of 125 .

(a) Starting from the number 2017 , what is the smallest number we
can reach with a sequence of these operations?
(b) What is the smallest number from which we can start, and reach
the number 2017 with a sequence of these operations?

6. Find a list of positive rational numbers, q_1 , q_2 , … , q_n
whose product is 1 , and whose sum is 2017 . Make your list as
short as possible.
Extra Credit: Prove that you have the shortest possible list.

Michael Reid’s Happy New Year Problems, 2020

Posted by permission of Michael Reid. Enjoy!

New Year’s Greetings!

Here are some fun puzzles to start the year.

1. Substitute the numbers 1, 2, … , 9 for the letters
a, b, … , i in the expression a^b + c^d + (e + f + g - h)^i
to get 2020.

2. Use the digits 1, 2, … , 9 in order, and any of the usual
arithmetic operations and parentheses to get a number that is
as close as possible to, but not exactly equal to 2020.

3. Express 2019/2020 as a sum of distinct Egyptian fractions,
i.e. 1 / n_1 + 1 / n_2 + ... + 1 / n_k for integers 0 < n_1 < n_2 < ...  n_k < 202049
(but 202049 is not square).

5. Make a 4×4 matrix of single-digit integers (0-9) with digits
2, 0, 2, 0 on the main diagonal, and having determinant 2020.
Is it possible to do it with a symmetric matrix?

If you liked this one, check out other puzzles ont this blog tagged with “Michael Reid”.

Questions about quadratic residues

Let P denote the set of all primes and, for p \in P, let (*/p) denote the Legendre quadratic residue symbol mod p. Let {\mathbb N}=\{1,2,\dots\} denote the set of natural numbers and let

L: {\mathbb N}\to \{-1,0,1\}^P,

denote the mapping L(n)=( (n/2), (n/3), (n/5), \dots), so the kth component of L(n) is L(n)_k=(n/p_k) where p_k denotes the kth prime in P. The following result is “well-known” (or, as the joke goes, it’s well-known to those who know it well:-).

Theorem: The restriction of L to the subset {\mathbb S} of square-free integers is an injection.

In fact, one can be a little more precise. Let P_{\leq M} denote the set of the first M primes, let {\mathbb S}_N denote the set of square-free integers \leq N, and let

L_M: {\mathbb N}\to \{-1,0,1\}^{P_M},

denote the mapping L_M(n)=( (n/2), (n/3), (n/5), \dots, (n/p_M)).

Theorem: For each N>1, there is an M=M(N)>1 such that the restriction of L_M to the subset {\mathbb S}_N is an injection.

I am no expert in this field, so perhaps the following question is known.

Question: Can one give an effective upper bound on M=M(N)>1 as a function of N>1?

I’ve done some computer computations using SageMath and it seems to me that

M=O(N)

(i.e., there is a linear bound) is possible. On the other hand, my computations were pretty limited, so that’s just a guess.

Michael Reid’s Happy New Year Puzzle, 2012

Here is another puzzle from Michael Reid on NOBNET. (Michael also notes that if you find a solution (a,b,c,d,e,f) then (d,e,f,a,b,c) is another solution.)

Puzzle: Replace a, b, c, d, e, f with the first six prime numbers, in some order, to make the expression a\cdot b^c + d \cdot e^f equal to the New Year.

Best wishes for a happy, healthy and prosperous New Year!

Michael Reid’s Digit operation puzzles

Michael Reid (http://www.math.ucf.edu/~reid/index.html) posted these questions on Nobnet recently. I’m reposting them here.

Consider two rules for modifying a positive integer:

i) replace a substring of its digits by the square of the number represented by the substring
ii) if a substring is a perfect cube, replace the substring by its cube root

Neither the substring being replaced, nor the string replacing it may have leading zeroes.

For example, starting with 123, we may square `23′ to obtain 1529. Then we can square `29′ to get 15841, then square `5′ to get 125841, and then we could take the cube root of `125′ to get 5841, and so on.

What is the smallest number we can obtain from the number 2011 with a sequence of these operations?

Now suppose the two operations are instead

iii) replace a substring by its cube
iv) replace a substring which is a square by its square root

What is the smallest number we can get with these operations if we start from 2011?

Here is another “digit operations” puzzle that I hope you will find a nice challenge.

Consider two rules for modifying a positive integer:

i) replace a substring of its digits by 7 times the number represented by the substring
ii) if a substring is a perfect 7th power, replace the substring by its 7th root

Neither the substring being replaced, nor the string replacing it may have leading zeroes.

For example, starting with 347, we may replace the substring `34′ by `238′ (multiplying by 7) to obtain 2387. Then we can multiply the substring `3′ to get 22187. Now we can take the 7th root of `2187′ to get 23, and so on.

What is the smallest number we can obtain from the number 2011 with a sequence of these operations?

Now suppose the two operations are instead

iii) if a substring is divisible by 7, we may divide the substring by 7
iv) replace a substring by its 7th power

(which are the reverses of operations i) and ii) above).

What is the smallest number we can get with these operations if we start from 2011?