Score: 108

$2021=sqrt\left(sqrt\right(sqrt\left(sqrt\right(sqrt\left(sqrt\right(2^{3!!}\left)\right)\left)\right)/2\left)\right)-3^3$

This is a variant on $2^{11}-3^3$ but we get $11$ via $(3!!/2/2/2/2-1)/2/2$, where we implement divide by 2 with sqrt.

1

First, I claim that for any prime q, it is possible to choose one of q + 1 outcomes with just one coin. I do this as follows:

• Let p be a probability such that $$p^q+(1-p{)}^q=\frac{1}{q+1}.$$ (Such a p exists by the intermediate value theorem, since p = 0 gives a value that's too large and p = 1/2 gives a value that's too small.)
• Flip a coin that has probability p of coming up heads exactly q times. If all flips are the same, that corresponds to outcome 1. (This has probability 1/(q + 1) by construction.)
• For each k between 1 and q - 1, there are $$(\frac{q}{k})$$ ways of getting exactly k heads out of q flips, all equally likely. Note that this quantity is divisible by q (since none of 1, ..., k are divisible by q; this is where we use that q is prime). Thus, we can subdivide the particular sequences of getting k heads out of q flips into q equally-sized classes, for each k. Each class corresponds to an outcome (2 through q + 1). The probability of each of these outcomes is $$\frac{q}{q+1}\cdot \frac{1}{q}=\frac{1}{q+1},$$ which is what we wanted.

Now, note that 2021*12 - 1 = 24251 is prime. (I found this by guessing and checking.) So do the above for q = 24251. This lets you flip a coin 24251 times to get 24252 equally likely outcomes. Now, since 24252 = 2021*12, just assign 12 of the outcomes to each person. Then each person will have a 1/2021 chance of being selected.

If you're only allowed to use one coin, it is impossible to do this with fewer than 24251 flips in the worst case.

What if you can only use coins with rational probabilities?

The first puzzle got me into an optimization mindset -- and it seems to be the right mindset for that problem -- but the optimal solutions to P2 and P3 (which I missed before reading spoilers) are "crisp" or "a neat trick" rather that a result of whatever matches a (however clever) "optimization process" for me. (If this was intended, I really appreciate the subtlety of it, Scott!)

By "optimal*" I mean definitely cheapest formulas among all formulas using only natural numbers smaller than ${10}^{1000}$as intermediate values (and modulo any bugs in my code). You can find the code here and the solutions for all numbers 1..10000 here (obvious spoilers).

The largest intermediate value needed for all of those is below ${10}^{220}$. Note the code also finds optimal* formulas for many more values (~100 million on 50GB RAM), just does not report them by default. 

I have ran the code to also consider intermediate values up to ${10}^{10000}$ and even ${10}^{100000}$ and did not find any cheaper solution for numbers up to 10000. (In those runs my code got to the optimal solutions for only 98% and 88% (respectively) of the numbers up to 10000, not finding any better solutions, then ran out of memory. I still consider it a good indication that much larger values are likely not useful for numbers up to 10000.) I would be really interested in constructions or intuitions why this may or may not be the case!

I know about at least one case of a formula using real numbers as intermediates that is (very likely) strictly better that any formula with only natural intermediate values. That example is due to Scott -- leaving it up to him to disclose it or not.

2021 = (isqrt(isqrt((isqrt(isqrt(isqrt(isqrt((2 ** fact(fact(3))))))) // 2))) - (3 ** 3)) -- a cost-108 variation on $2^{11}-3^3$ that uses a clever cost-12 formula for $2^{11}$. This uses $5.5e216$ as an intermediate value -- the highest (up to small variations) encountered in formulas for values under 10000. This sub-formula is used in 149 of the 10000 solutions. My code prefers solutions with the smallest intermediate values used as a secondary criterion, so these large intermediate values are necessary for optimal* solutions.

Other encountered sub-formulas using large intermediate values: 7381 = (fact((2 + fact(5))) // (2 * fact(fact(5)))) (needs $1e203$, used 10 times in 1..10000), 3782 = (fact(((2 ** fact(3)) - 2)) // fact((fact(5) // 2))) (needs 3e85, used once), 1189 = isqrt(((2 // 2) + (fact((fact(3) ** 2)) // fact((2 ** 5))))) (needs 4e41, used once), and 32768 = isqrt(isqrt(isqrt((2 ** fact(5))))) (needs 1e36, used 56 times). All other optimal* solutions for values up to 10000 only use intermediate values smaller than ${10}^{10}$.

The distribution of used intermediate values -- only 3 between ${10}^{10}$ and ${10}^{100}$, 2 more under ${10}^{300}$, and no more under ${10}^{100000}$ -- is my main argument for all the found solutions for 1...10000 being likely optimal. Anything to the contrary would be intriguing indeed!

$N=-{\log }_2{\log }_2\sqrt{\sqrt{\dots \sqrt{2}}}$ using $N$ nested square-roots.

After 2 dice rolls of $dA$, $dB$, partition the $AB$ outcomes into $N=2022$ equally-sized sets, and $C=AB\text{mod}N$ remaining outcomes. If you hit one of the $N$ sets, you are done. If not, you can use the remaining information as already having thrown a $dC$ and only throw one additional dice (if C>2) before you do another partition of the outcomes into $N$ sets and a remainder (rather than doing a full restart). (Note that it is generally better to be left with a larger $C$ when the probability of spillover is comparable.)

This can be represented by a recursive formula for ${EAR}_N\left(A\right)$: "expected additional rolls if you already have thrown dA", the puzzle result is then ${EAR}_{2022}\left(1\right)$. Rather than the full formula, here is a program that iteratively computes $EAR$. My result is $2.0000005791099$, matching other similar solutions here. (See Vaniver's comment for the optimal one)

There are some reductions between coins and emulated dice. (Note $d1$ is trivially available.) 

• Reduction 1: If you can emulate $dA$ and $dB$, you can emulate $dAB$ (trivial).
• Reduction 2: If you can emulate $dA$, you can emulate dice of any divisor of $A$ (trivial).
• Reduction 3: If you can emulate $dA$ and $dB$, you can emulate $d(A+B)$ with additional $A/(A+B)$-coin (flip the $A/(A+B)$-coin, then emulate $dA$ or $dB$). In particular, you can emulate $d(A+1)$ using $dA$ and one extra coin.

This then gives a few solutions to 2021 using only rational coins and a range of general solution schemas to explore:

• Using $k$ different coins, one can emulate $dA$ where $A$ is a number with $k$ ones in its binary representation (start with 1, use R1 with $d2$ to append "0" binary digit and R3 to add "1" binary digit) as well as all its divisors (R2). 2021 divides $68987912193=2^{36}+2^{28}+2^0$, we use 3 coins: 1/2, 1/257, 1/68987912193. (One can look for low-binary-1 multiples of a number with binary residuals and some branching.)
• Find $a,b,c,d\ge 0$ such that $N|2^a{3}^b+2^c{3}^d$ (3 coins) or $N|2^a{5}^b+2^c{5}^d$ (3 coins, 5=2^2+1) etc. 2021 divides $2^{10}{5}^{27}+1$.
• Yet another solution for 2021 is to go from needing $d2021$ to $d2020$ via a $1/2021$-coin, then to $d505$ via $d2$, then notice that $505|2^{50}+1$. This also implies some possible schemas.

I don't know about a fully-general (and guaranteed to halt) algorithm using just R1-R3, since it is not clear how high you need to go in the multiples to split via R3. There may also be other reduction rules even for just rational coins. I would be curious about any thoughts in that direction!

• For any argument, you can assume any schema is "static": it throws a fixed sequence of coins regardless of intermediate results. (Proof: Take an arbitrary decision tree with its leaves grouped into $N$ groups of equal probability. Inserting a new coin-flip anywhere in the tree (branching into two identical copies of its former subtree) preserves the resulting groups-distribution. Obtain a tree with single-coin levels starting at the root.)
• Any finite set of rational-probability coins of the form $p=a/b$ with $a$ natural and $b$ odd (i.e. without a 1/2-coin) can't emulate any dice (proof via expansion of all the probability terms with a common denominator in a static decision tree; exactly one of these terms is odd) (a simpler proof shows this for single rational $a/b$-coin for $a/b\ne 1/2$ using binomial expansion of $(a+(b-a){)}^k/b^k$).
• Therefore using only rational coins, the only 1-coin-expressable dice are $d\left(2^k\right)$. I suspect that the only 2-coin-expressable dice are divisors of $2^a+2^b$ for some $a,b\ge 0$.
• Any set of coins with transcendental and algebraically independent probabilities (i.e. numbers that are not roots of any multi-variate polynom with rational coefficients, e.g. $\{e,\pi \}$) can't emulate any dice (proof using the "not-roots-of-any-rational-polynomial" definition on the expansion of leaf probabilities of a static decision tree).

[new]:
Roll a d1697 (which is prime, I double-checked). Either the result is in the first 674 (337*2), or the middle 1011 (337*3), or the last 12 (2*2*3).
If it's in the first 674, you now need to roll a d3 to figure out whether it's 1-674, 675-1348, or 1349-2022.
If it's in the middle 1011, you now need to roll a d2 to figure out whether it's 1-1011 or 1012-2022.
If it's in the last 12, you need to mod 6 and then roll a d337 to figure out whether it's 1-337, 338-674, etc.
---
[edit: shown wrong by kuhanj]
Roll a d1089. Either the result is in the first 1011, or the latter 78.
If in the 1011, roll a d2 to determine whether they're in 1-1011 or 1012-2022.
If in the 78, mod by 6 to get a number between 0 and 5, which determines whether the winner is in 1-337, 338-674, etc; now roll a d337 to determine which one in the group. Two rolls, guaranteed.
---
[original, shown wrong by Measure] Can't you just roll a d2 and a d1011, which identifies the relevant person in two rolls guaranteed? (i.e. the d2 tells you whether they're in 1-1011 or 1012-2022, and then the second roll tells you which person.)
I don't think you can do better than this, because there's no way to do it in 1 roll (you need a die of size 2022), and I don't think there's a way to do it in less than 2 rolls (because while you can use your first roll to switch what your second roll will be, you can't allocate probability on the first roll such that you don't need a second roll, because otherwise you won't be uniformly selecting from all of the people). 

So here's a partial sketch pointing towards a solution, but it needs a lot of work and maybe more coins.

Pick p=1/2, and generate a binary string of length 11 with 11 flips. If it's in the first 2021 numbers, that identifies your person. If it's not, subtract 2021 to get a number between 0 and 26, and repeat. [This doesn't have an upper bound yet.]

Line of attack one: shift p such that you can make a very long string which does divide into 2021 parts evenly. I think this ends up being a giant pain because you need to carefully adjust for the different probabilities of all of the different table elements. [Edit: Unexpected_Values found this solution [LW(p) · GW(p)] and had an elegant proof of it.]

Line of attack two: shift the number of flips such that the remainder ends up a multiple of 43 (and separately) 47. If you can get both, then you can do the first series of flips, stop if it identifies someone and save the remainder mod 43 if it doesn't, and then do the second series of flips, which either identifies someone directly or gives you a remainder mod 47, and then the two remainders identify someone, and you have an upper bound. [Some brief searching through numbers in python makes me somewhat pessimistic that this will work.]

 Toss dice 1811 and 1907. (1811*1907)%2022=1 so you can divide the possibilities into equal piles with only 1/3453577 chance of getting the leftover. If you do get the leftover, repeat the procedure. Expected number of roles 2.000000579

Note that you must always toss at least 2 dice to make this game fair. Any strand of possibility where you only have one dice is too likely.

I bruteforce searched for pairs of primes to minimize (p*q%2022)/(p*q) (the chance of needing to repeat) and these were it.

The prime factors of 2022 are 2, 3, and 337.  Any method of selecting 1 person from 2022 must cut the space down by a factor of 2, and by a factor of 3, and by a factor of 337 (it does not need to be in that order and you can filter down by more than one of those factors in single roll, but you must filter down by each of those in a way where the probability is uniform before starting).

The lowest it could be is 2 rolls.  If someone could win on the first roll, that person’s probability of winning could be no less than 1/(Number of sides of the first roll die).  Since the die with the most sides has 2017, that person’s probability to win would be more than 1/2022, so the probability of winning could not be even for everyone.

To get it in 2 rolls:

Before the start of the dice rolling, divide the group of 2022 using 3 different groupings:

• Grouping A:  Divide the 2022 people into 674 sub-groups of 3 people each (Group A1, Group A2, … Group A674)
• Grouping B:  Divide the 2022 people into 1011 sub-groups of 2 people each (Group B1, Group B2, … Group B1011)
• Grouping C:  Divide the 2022 people into 6 sub-groups of 337 people each - but differentiated by 0-indexed numbers that correspond to modulo amounts (Group C0, Group C1, Group C2, Group C3, Group C4, and Group C5)

Each person will be a member of exactly 1 A group, exactly 1 B group, and exactly 1 C group.

For the first roll, roll the die with 1697 sides.

If the number is between 1 and 674 (inclusive):    

1.     Select the A group whose number corresponds to the number of the die.
2.     Roll the 3-sided die to select a winner from among that group.

If the number is between 675 and 1685 (inclusive):    

1.     Calculate: ((Number on the die) - 674) to get a number between 1 and 1011 (inclusive)    
2.     Select the B group whose number corresponds to the ((Number on the die) - 674) number.    
3.     Roll the 2-sided die to select a winner from among that group.

If the number is between 1686 and 1697 (inclusive):    

1.     Calculate: (((Number on the die) - 1685) modulo 6) to get a number between 0 and 5 (inclusive)    
2.     Select the C group whose number corresponds to the (((Number on the die) - 1685) mod 6) number.
3.     Roll the 337-sided die to select a winner from among that group.

So on this calculation, the expected number of rolls is exactly 2, since for each possible outcome on the first one, there is a second die to throw that will select the winner.