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 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, 2021=2∗103+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 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 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 ∼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 2021 people total. This time, you plan ahead, and decide to buy some weighted coins before the party. For any number p∈(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 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/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 2021 sided die, flip the 1/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.
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 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, 2021=2∗103+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 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 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 ∼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 2021 people total. This time, you plan ahead, and decide to buy some weighted coins before the party. For any number p∈(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 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/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 2021 sided die, flip the 1/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.