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