Are You Clever Enough?

Riddler Express

You are very clever when it comes to solving Riddler Express puzzles. You are so clever, in fact, that you are in the top $10$ percent of solvers in Riddler Nation (which, as you know, has a very large population). You don’t know where in the top $10$ percent you are — in fact, you realize that you are equally likely to be anywhere in the topmost decile. Also, no two people in Riddler Nation are equally clever.

One Friday morning, you walk into a room with $nine$ members randomly selected from Riddler Nation. What is the probability that you are the cleverest solver in the room?

Solution

Without loss of generality we can assume that the normalized IQ of the population follows the Uniform distribution $\mathcal{U}[0,1]$.Let $X_1, X_2, \dots, X_n$ be the random variables representing the IQs of the other individuals in the room apart from you where $X_i \sim \mathcal{U}[0,1]$ for $i \in \{1,\dots,n\}$. Let $Y \sim \mathcal{U}[a,b]$ be the random variable representing your IQ where $0 \leq a < b \leq 1$. We need the probability $\mathbb{P}[ X_{(n)} < Y ]$ where $X_{(n)}= \max(X_1,\dots, X_n)$. From Order Statistics of the Uniform distribution, we know that $\mathbb{P}[X_{(n)} < y ] = y^n$. Therefore the required probability is given by

When $n=9, a= 0.9$ and $b=1.0$ the required probability is $\textbf{0.65132}$.

Computational Solution

From the simulation below, we can see that the required probability is indeed $\approx \textbf{0.651}$.

import numpy as np

def prob_you_cleverest(n, start_iq = 0.9, end_iq = 1.0, runs = 5000000):
    others_iqs = np.random.rand(runs, n)
    your_iqs = np.random.uniform(start_iq, end_iq, runs)
    return np.mean(np.where(np.max(others_iqs, axis=1) < your_iqs, [1], [0]))

print(prob_you_cleverest(9))

Riddler Classic

You have four standard dice, and your goal is simple: Maximize the sum of your rolls. So you roll all four dice at once, hoping to achieve a high score.

But wait, there’s more! If you’re not happy with your roll, you can choose to reroll zero, one, two or three of the dice. In other words, you must “freeze” one or more dice and set them aside, never to be rerolled.

You repeat this process with the remaining dice — you roll them all and then freeze at least one. You repeat this process until all the dice are frozen.

If you play strategically, what score can you expect to achieve on average?

Extra credit: Instead of four dice, what if you start with five dice? What if you start with six dice? What if you start with $N$ dice?

Computational Solution

Let the number of dice be $N$, a roll can be represented as an $N$-tuple $(d_1, d_2, \dots, d_N)$ where $d_i \in \{1,\dots, 6\}$ for $i \in \{1,\dots, 6\}$. There are a total of $6^N$ possible rolls. Let $MES(roll)$ be the function which gives you the maximum expected score that can be achieved starting from a given roll by choosing to reroll zero, one, two or $N-1$ dice. The expected maximum score is then given by

where $roll \in \\{(d_1,d_2,\dots, d_N) \lvert d_i \in \\{1,\dots,6\\}, i \in \\{1, \dots, N\\} \\}$.

For a given roll $(d_1, d_2, \dots, d_N)$, let $(d_{s(1)}, d_{s(2)}, \dots, d_{s(N)})$ be the corresponding tuple sorted in $\textbf{descending}$ order.

The maximimum expected score that can be obtained by following the optimal strategy starting from a given initial roll can be calculated as follows:

1. We first freeze the maximum value of a roll $d_{s(1)}$.

2. We then calculate the maximum expected score that can result by rerolling $0, \dots, N-1$ remaining dice. If we are rolling $j$ dice, the maximum expected score is the sum of the expected maximum score for those dice $EMS(j)$ and the top $N-1-j$ of the remaining values of the roll after removing the maximum value which was already frozen.

This leads to the following definition of the function $MES$:

where $j$ stands for the number of dice that are rerolled.

From the above it is clear that $EMS(N)$ is ultimately defined in terms of $EMS(0)=0, EMS(1), \dots, EMS(N-1)$ and it can be calculated iteratively.

Using the code below, we see that the maximum score that can be achieved on average is $\textbf{989065/52488=18.843}$.

from itertools import product
from fractions import Fraction

def MESs(num_dice):
    exp_max_scores = {}
    exp_max_scores[0] = 0
    for n in range(1, num_dice+1):
        total_mes = 0
        for roll in product(range(1, 6 + 1), repeat = n):
            sorted_roll = sorted(list(roll), reverse=True)
            total_mes += max(sum(sorted_roll[:n-j]) + exp_max_scores[j] for j in range(n))
        exp_max_scores[n]=Fraction(total_mes, 6**n)
    return exp_max_scores

mess = MESs(5)
for i in range(1,5):
    print(f"The average max score for {i} dice is {mess[i]}")

The average max score for 1 dice is 7/2
The average max score for 2 dice is 593/72
The average max score for 3 dice is 13049/972
The average max score for 4 dice is 989065/52488