Logic Puzzle: More Simulated Dice

The “Prime Sided Dice” logic puzzle was all about simulating fair dice using other fair dice. In this puzzle, we limit ourselves even further and try to simulate a fair die using only coins.

Imagine you have k coins, which are not necessarily fair. You get to choose the bias for each of the coins. (i.e. You choose the probability that each coin comes up heads.) You may then use whatever procedure you like to simulate a fair n-sided die. You are allowed to flip the same coin more than once. The catch is that your procedure must end in some bounded number of coin flips.

For example, if you have a coin that comes up heads with probability 1/3, and another coin that comes up heads with probability 1/2, then you can simulate a 3-sided die by flipping the first coin, returning 1 if you get heads, and otherwise flipping the second coin and returning 2 or 3 depending on the result.

As a function of n, what is the minimum number k of coins that you need? (i.e. Which dice can be simulated with 1 coin? 2 coins? 3 coins? etc.)

The solution will eventually be posted in the comments. If you have been working on this puzzle for a while, and are starting to lose interest, please make sure you view this minor hint before you give up. I advise anyone who has been working on this puzzle for more than an hour to just view the hint. It is more interesting than it is helpful. (Written in rot13, decode here.)

Gurer rkvfgf na vagrtre x fhpu gung rirel qvr pna or fvzhyngrq hfvat ng zbfg x pbvaf.

Logic Puzzle: Count the Flags

You are tasked with designing a robot to explore a large but finite maze. The maze is drawn on a square grid, and walls exist on some of the edges of the square grid. Some of the squares contain a flag.

Your robot may interact with the world in the following ways:

1) Check which of the 4 adjacent edges contain walls.

2) Move to one of the 4 adjacent squares (provided there is no wall in the way).

3) Check if there is a flag on your square.

4) Pick up a flag (provided there is a flag on your square and the robot is not already holding a flag).

5) Put down a flag (provided the robot is holding a flag and there is not already a flag on your square).

6) Generate a random bit.

7) Output a number.

Your robot will be placed in a maze. The maze will contain some number of flags (from 100 to 1000). All flags will be reachable from the robot’s starting position. Your robot is tasked with determining the number of flags. The robot may take as long as it needs, but may only output one number and must output the correct answer eventually, with probability 1.

The catch is that your robot is not Turing complete. It only has a finite amount of memory. You can give your robot as much memory as you need, but it must succeed on arbitrarily large mazes.

As always, the solution will eventually be posted in the comments, but you are encouraged to show off by posting your solution first.

Logic Puzzle: 5, 5, 7, 7 = 181

If you have not already solved the puzzle “One, Two, Three,” you should solve that one first. It is a warm-up for this one.

Using the numbers 5 and 7, each twice, and the combining them using addition, subtraction, multiplication, division, exponentiation, square root, factorial, unary negation, and/or parenthesis, but no base 10 shenanigans like digit concatenation, come up with an expression which evaluates to 181.

The solution will eventually be posted in the comments, but if you solve it before then, feel free to show off.

Logic Puzzle: One, Two, Three

Using the three digits, 1, 2, and 3, each at most once, and the combining them using addition, subtraction, multiplication, division, exponentiation, square root, factorial, unary negation, digit concatenation, decimal point, vinculum, and parenthesis, construct all the positive integers from 1 to 30. (Digit concatenation and decimal points only allowed on the original 3 digits. You do not need a 0 before the decimal point.)

The solution will eventually be posted in the comments, but if you solve it before then, feel free to show off (even with partial progress).

Logic Puzzle: Upside Down Cake

Imagine you have a circular cake, that is frosted on the top. You cut a d degree slice out of it, and then put it back, but rotated so that it is upside down. Now, d degrees of the cake have frosting on the bottom, while 360 minus d degrees have frosting on the top. Rotate the cake d degrees, take the next slice, and put it upside down. Now, assuming the d is less than 180, 2d degrees of the cake will have frosting on the bottom.

If d is 60 degrees, then after you repeat this procedure, flipping a single slice and rotating 6 times, all the frosting will be on the bottom. If you repeat the procedure 12 times, all of the frosting will be back on the top of the cake.

For what values of d does the cake eventually get back to having all the frosting on the top?

The solution will eventually be posted in the comments, but if you solve it before then, show off and post your own solution.

Logic Puzzle: Pandigital e

If you can construct a number using the digits, 0,1,2,3,4,5,6,7,8, and 9 each exactly once and the operations of addition, subtraction, multiplication, division, exponentiation, and digit concatenation, in any order, we will call that number pandigital. Notice that there are only finitely many pandigital numbers.

How close can you get to the mathematical constant e $=\sum_{n=0}^\infty \frac{1}{n!}$ with a pandigital number?

There are two parts to this logic puzzle. First, try to get the best approximation of e that you can. Then, try to come up with an estimate of how close you can get if you checked all possible pandigital approximations. I will post one particularly good approximation in the comments, but I suggest you think about it for a while before looking.

Logic Puzzle: Poker Interrupted

Imagine you and four friends deal out a hand of a game of poker, and look at your hands. Each person is dealt 5 cards, and the remaining 27 cards are still in the deck. Unfortunately, the game is interrupted before it has a chance to start. You decide to memorize your hands, and play the hand tomorrow. The next day, you want everyone to somehow get the same 5 cards they had yesterday out of a shuffled deck, without gaining any information about what cards the other players have. All players are assumed to be honest, and will not cheat in any way.

This puzzle is my own design. I will eventually post the solution in the comments, but if you solve it before then, show off and post your own solution.