2021 New Year Optimization Puzzles

[Scott Garrabrant]

I was asked to host a puzzle corner for the New Year Eve’s Ultra Bash, which would be a Schelling time/​place for people to talk about and solve puzzles together. For the event, I decided to make three 2021 themed optimization puzzles, and I decided to also share them here. For each of these puzzles, you are trying to make a number small. Use spoiler boxes in the comments. Feel free to PM me answers, or come chat with me at the party, and I will let you know whether or not you can do better. (I won’t let you know if you can do better unless you explicitly ask.) Happy New Year!

Puzzle 1

Construct a formula for $\text{2021}$ using natural numbers $2$ or greater, and the operations addition, subtraction, multiplication, division, exponentiation, unary negation, square root, and/​or factorial. (You may also use parentheses.) Your score is the product of the numbers used in your expression. Operations are free. If you use a number multiple times, you have to count it multiple times. Your goal is to minimize your score.

For example, $\text{2021}=2\ast {10}^3+4!-3$ gives you a score of $720$. You can do better.

Puzzle 2

You decide to run a donor lottery party for yourself and $\text{2021}$ of your friends. You each put in $10.00 dollars, and one “lucky winner” (chosen uniformly at random) will have to decide how to spend the $20,220.00. However, your only sources of randomness are dice with prime numbers of sides. For each prime $p$ strictly between $1$ and $\text{2021}$, you have a weirdly shaped fair die with $p$ sides. You may only roll one die at a time. Your timelines are short, so you decide to choose the winner as quickly as possible (in expectation). How small can you make the expected number of die rolls needed to determine the winner?

For example, you could roll the $2017$ die twice to get a number between $1$ and $4068289$. If the number is at most $4068264$, you take the result mod $2022$. If the number is in the range $4068265-4068289$, reroll. This procedure takes $\sim 2.00001229025$ rolls in expectation. You can do better.

Puzzle 3

You decide to run another donor lottery party. The person who won the last donor lottery party is still deciding how to spend the money and will not participate, so you have $\text{2021}$ people total. This time, you plan ahead, and decide to buy some weighted coins before the party. For any number $p\in (0,1)$, you can buy a coin that comes up heads with probability exactly $p$. Try to find a procedure that uses as few coins as possible to choose one of the $\text{2021}$ people uniformly at random. Your procedure can take as long as you like, and you can flip the same coin more than once, but you must be able to give a worst-case upper bound for how long your procedure takes.

For example, you could use the following dice: $p=1/\text{2021}$, $p=1/505$, $p=1/63$, $p=1/31$, $p=1/15$, $p=1/7$, $p=1/3$, and $p=1/2$. To simulate a $\text{2021}$ sided die, flip the $1/\text{2021}$ coin. If it comes up heads, you are done, otherwise, you need to simulate a $2020$ sided die. Do this by flipping the $1/2$ coin twice, and simulating a $505$ sided die. The simulation of the $505$ sided die is similarly done by flipping the $1/505$ coin and possibly simulating a $504$ sided die, and so on. This procedure uses 8 coins. You can do better.

[James Payor]

My best so far on puzzle 1:

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.

[Scott Garrabrant]

This comment is the best I can do on puzzle 1. Read it only if you want to be spoiled.

[Scott Garrabrant]

Also, here is a hint on puzzle 1, you could read first:

I believe the above answer is optimal. It only passes through natural numbers in its intermediate computations. I believe it is impossible to match the score of the above solution if you limit yourself to natural numbers below a googol.

[Eric Neyman]

Puzzle 3 thoughts: I believe I can do it with

1

coins, as follows.

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 = ¹⁄₂ 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.

Conjecture (maybe 50% chance of being true?):

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

Question:

What if you can only use coins with rational probabilities?

[Scott Garrabrant]

This comment is the best I can do on puzzle 3. Read it only if you want to be spoiled.

[Tomáš Gavenčiak]

A beautiful solution! Some remarks and pointers

Note that your approach only works for target $N>3$ (that is $q>2$), as $p^2+(1-p{)}^2=1/3$ does not have a real solution. Open question: How about 1-coin solution emulating a 3-sided dice?

See my solution (one long comment for all 3 puzzles) for some thoughts on rational coins—there are some constructions, but more importantly I suspect that no finite set of rational coins without the 1/​2-coin can generate any fair dice. (My lemma does not cover all rational coins yet, though; see by the end of the comment. I would be curious to see it turn out either way!)

[Tomáš Gavenčiak]

Update: I believe the solution by @UnexpectedValues can be adapted to work for all natural numbers.

Proof: By Dirichlet prime number theorem, for every $N$, there is a prime $q$ of the form $q=(N-1)+kN$ as long as N-1 and N are co-prime, which is true whenever $N>2$. Then $N|q+1$and the solution by UnexpectedValues can be used with appropriate $p$. Such p exists whenever $q>2$which is always the case for $N>3$. For $N=3$, one can take e.g. $q=5$ (since $3|5+1$). And $N\le 2$ is trivial.

[Tomáš Gavenčiak]

So, I got nerd-sniped by this (together with my flatmate on P3) and we spent some delicious hours and days in various rabbit-holes. Posting some thoughts here.

First of all, a meta-comment (minor spoiler on the nature of best-known solutions):

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!)

Puzzle 1

For P1, I got a bit over-board and found optimal* solutions for numbers up to 10000 (and some more, with some caveats—see below). The spoiler-tags just below do not contain the solutions, but spoilery notes on my approach, actual solutions are lower down.

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.

My solution for 2021 and some notes on optimal* solutions for other numbers

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!

And a universal cost-8 solution if $\log$ was allowed:

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

Puzzle 2

My (non-optimal) solution, more for reference and the algorithm that anything else. (“dN” denotes an N-sided fair die.)

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)

Puzzle 3

While me and Adam did not find the best known solution for P3, we had a lot of fun trying to figure out various approaches to and properties of the problem. Here is a short summary, happy to share more details. The framing here is “emulating dN” (an N-sided fair dice).

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: ¹⁄₂, ¹⁄₂₅₇, ¹⁄_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!

And few more theoretical observations.

• 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).

[Vaniver]

Puzzle 2 (I now think my approach is actually right):

[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).

Puzzle 3:

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 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.]

[kuhanj]

Re problem 2:

1089 isn’t prime either (1089 is 9*121). I think this approach might not work in general because of the two relevant numbers for the first die needing to share a factor. The first prime has to be of the form A+B, where A= 2022/​(prime divisor of 2022), and B = number that is a multiple of 2022/​(product of 2 its primes) for the above method to work. But no such prime exists since A must be divisible by two of (2,3, 337), and B must also be divisible by two of (2,3, and 337), so they must share at least one non-one factor, and can’t be prime.

[Scott Garrabrant]

Oh, yeah, oops, I didn’t read it well enough. Anyway, it is right now, so ill leave my comment endorsing it.

[Vaniver]

[I edited in spoiler tags to the above comment.]

Well, I would clearly not last long among the pebble-sorters. I think your criticism is almost right.

Unless we can come up with some scheme whereby there’s only one prime left for particular regions, which I think would require 2*337+3*337+n*2*3 to be prime, which it looks to me like 1697=337*5+12 is.

[Scott Garrabrant]

This comment contains the best I can do on puzzle 2. Read it only if you want to be spoiled.

[Measure]

1011 is not prime.

[Vaniver]

That’s what I get for searching for ‘factors’ instead of ‘prime factors’!

[Rafael Harth]

Possible solution for P1:

$\sqrt{2^{4!-2}}-3^3$ for a score of 14 (now 144 with multiplicative scoring, but it’s still the lowest among the solutions I’ve found)

[Scott Garrabrant]

I changed the scoring, so now $\sqrt{2^{4!-2}}-3^3$ scores 144.

[Donald Hobson]

For question 2, I have an answer that I think is optimal

Toss dice 1811 and 1907. (1811*1907)%2022=1 so you can divide the possibilities into equal piles with only ¹⁄_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.

[Charlie Steiner]

FYI, I made my code a little more optimal and ran it overnight—I didn’t find any scores smaller than what I already knew about, after searching through everything with only up to 1 square root and 2 factorials, never using any numbers larger than 16!.

[Vaniver]

This procedure uses 8 dice.

Presumably you mean coins?

[Scott Garrabrant]

Yeah, I changed it, thanks

[Measure]

I wonder

if there is a solution to Puzzle 1 of the form: √√√√√√√...(3!!!!!!!… ± 3)

[Richard_Kennaway]

Summary results (without derivations):

Puzzle 1: score 19. Edit: that was for score = sum of numbers used. The product score for the same solution is 198.

Puzzle 2: 1.0030 expected rolls.

Edit: Scott pointed out that the primes had to be below 2021. For this I have a solution with exactly 2 rolls.

Edit, no, I’m still wrong, there are 2022 people to choose among, not 2021.

My latest attempt gets 2.000000579 expected rolls.

Puzzle 3: 4 coins (and at most 14 flips).

Full solutions:

Puzzle 1:

$2^{11}-3^3$ scores 19.

Edit: for the problem as originally stated, i.e. the score is the sum of the numbers used. For score = product, the score is 198.

Puzzle 2:

Use a die with 2027 faces (the smallest prime above 2021). Roll to choose; if the result is above 2021 roll again. The expected number of rolls is 2027/​2021 = 1.0030.

Edit: I missed the condition that the primes had to be below 2021. Since $2021=43\times 47$, use one roll each of a 43-sided and a 47-sided die.

Edit, no, I’m still wrong, there are 2022 people to choose among, not 2021. So I don’t have a solution to puzzle 2 yet.

New attempt: I used some computational assistance in finding this solution. Roll one die of 1811 sides and one of 1907. The product of these is 3453577 = 1708*2022 + 1. In 3453576 out of 3453577 cases this gives you your choice, otherwise roll both again.

Expected rolls = 2*(3453577/​3453576) = 2.000000579.

Puzzle 3:

Use six coins, with probabilities ¹⁄₂, ¹⁄₃, ¹⁄₅, 1024/​2021, ⁷²⁹⁄₉₉₇, and ²⁴³⁄₂₆₈.

Flip 1024/​2021 to divide the people into groups of 1024 and 997. Choose from the 1024 group with 10 flips of ¹⁄₂.

For the 997 group, use the ⁷²⁹⁄₉₉₇ to get groups of 729 and 268.

The 729 group can be chosen from with the ¹⁄₂ and ¹⁄₃ coins in at most 12 rolls. (Use ¹⁄₃ to cut off one third of the group, and ¹⁄₂ to split the remaining ²⁄₃ into two thirds. Do this 6 times.)

For the 268 group, use the ²⁴³⁄₂₆₈ to split it into groups of 243 and 25.

These can both be chosen from with the ¹⁄₂, ¹⁄₃, and ¹⁄₅ coins, the group of 243 with at most 10 flips, the group of 25 with at most 6.

In the worst case 14 flips are needed.

Better solution with five coins: 2000/​2021, ¹⁄₂, ¹⁄₃, ¹⁄₅, and ⁴⁄₇.

Use 2000/​2021 to divide the group into 2000 and 21. The ¹⁄₂ and ¹⁄₅ will choose from 2000 in at most 13 rolls. Use ¹⁄₃ and ¹⁄₂ to divide the 21 into three groups of 7. Use the ⁴⁄₇ to split 7 into 4 and 3, which can be chosen from with the ¹⁄₂ and ¹⁄₃.

Further improvement with four coins: 2000/​2021, ¹⁄₂, ¹⁄₅, and ²⁰⁄₂₁.

Use 2000/​2021 to divide the group into 2000 and 21. 2000 is as before, using the ¹⁄₂ and ¹⁄₅. For the group of 21, use ²⁰⁄₂₁, then the group of 20 can be solved with the ¹⁄₂ and ¹⁄₅.

Considering the way these solutions all work, I doubt if there is one with three coins along these lines. UnexpectedValues claims to do it with just one coin, so he must be taking a completely different approach. I want to think about that before looking at his solution.

[Scott Garrabrant]

Puzzle 2 does not allow primes over 2021

[Scott Garrabrant]

I changed the scoring, so now $2^{11}-3^3$ scores 198.

[Bruce G]

Here is the best I was able to do on puzzle 2 (along with my reasoning):

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.

[Roland Pihlakas]

If you would allow ceiling function then I could give you a solution with score 60 for the Puzzle 1. Ceiling or floor functions are cool because they add even more branches to the search, and enable involving irrational number computations too. :P Though you might want to restrict the number of ceiling or floor functions permitted per solution.

By the way, please share a hint about how do you enter spoilers here?

[Scott Garrabrant]

Typing >! at the start of a line makes a spoiler

I conjecture you can get every positive integer with cost 3 and a single floor function, but it also seems very hard to prove.

[Roland Pihlakas]

Yes, maybe the the minimum cost is 3 even without floor or ceiling? But the question is then how to find concrete solutions that can be proven using realistic efforts. I interpret the challenge as request for submission of concrete solutions, not just theoretical ones. Anyway, my finding is below, maybe it can be improved further. And could there be any way to emulate floor or ceiling using the functions permitted in the initial problem formulation?

By the way, for me the >! works reliably when entered right in the beginning of the message. After a newline it does not work reliably.

ceil(3!! * sqrt(sqrt(5! /​ 2 + 2)))

[Zolmeister]

Puzzle 1:

$3!!+3{!}^4+5$

score: 180

[Measure]

Puzzle 1

For the sum scoring rule:
2^(3!*2 − 1) − 3^3 = 2021 (14)

For the product scoring rule, I’m not sure I can do better than:
√(2^(4! − 2)) − 3^3 = 2021 (144)

Puzzle 2

Roll d1811 and d1907 for a number between 1 and 3453577. This upper bound is only 1 more than a multiple of 2022, so there’s only a ¹⁄_3453577 chance that a reroll will be needed. This results in an expected 2.0000005791 rolls.

Puzzle 3

This solution uses two coins, one with [1/​2], and one with [1/​2021].

1. Flipping [1/​2] eleven times can simulate a d2048. If the result is in 1-2021, then done. Otherwise, subtract 2021 to get a result in 1-27. Note that this result can be used to simulate a d3, d9, or d27.

2. Combining the previous result with seven more [1/​2] flips can simulate a d3456. If the result is in 1-2021, then done. Otherwise, subtract 2021 to get a result in 1-1435. Note that this result can be used to simulate a d5, d7, d35, d41, d205, d287, or d1435.

3. Repeating the above process allows us to simulate, among others, a d2, d3, d5, d7, d31, or d101. These can then be combined to simulate any of the coins from the example solution except the [1/​2021], which we already have.

4. The actual solution involves pre-computing the maximum number of each type of coin flip that could be needed to complete the example solution. Any time a result in 1-2021 is achieved, the process terminates immediately with that result. If all necessary coin flip results have been computed without terminating early, then proceed with the example solution using the pre-computed results as required in the order they were computed.

5. If there is a way to simulate a [1/​2021] coin with a [1/​2] coin, then only one coin is needed.

[Scott Garrabrant]

Puzzle 1 does not allow the use of 1 (also, I changed the scoring to the product rather than the sum)

[Measure]

Updated and added solutions for Puzzle 2 and Puzzle 3.