2021 New Year Optimization Puzzles

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 using natural numbers 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, gives you a score of . You can do better.

Puzzle 2

You decide to run a donor lottery party for yourself and 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 strictly between and , you have a weirdly shaped fair die with 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 die twice to get a number between and . If the number is at most , you take the result mod . If the number is in the range , reroll. This procedure takes 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 people total. This time, you plan ahead, and decide to buy some weighted coins before the party. For any number , you can buy a coin that comes up heads with probability exactly . Try to find a procedure that uses as few coins as possible to choose one of the 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: , , , , , , , and . To simulate a sided die, flip the coin. If it comes up heads, you are done, otherwise, you need to simulate a sided die. Do this by flipping the coin twice, and simulating a sided die. The simulation of the sided die is similarly done by flipping the coin and possibly simulating a sided die, and so on. This procedure uses 8 coins. You can do better.