bushindo

A permutation is a rearrangement of a list. For instance, suppose that we have a vector x = (A, B, C, D, E, F, G), and we have a permutation P = ( 7,6,5,4,3,2,1 ). If we apply P to y, we get the following P( y ) = (G, F, E, D, C, B, A). If we apply this particular permutation P twice to y, we get the original vector back P2( y ) = P( P( y ) ) = (A, B, C, D, E, F, G). Let's say that I have a 62-dimensional binary vector y. I also have another permutation P. I apply the consecutive powers of P to y, and list out the result. In the code block below, the 61 rows, starting from the first one, list out P0y, P1y, P2y, ....., P60y. Note that P has a cycle of 60, as P60y = y. The challenge is to find P from the data below. What is this permutation? 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0

That's correct. Nicely done!

That was fast. You are correct, good job. Maybe that was too easy. Here's a bonus question. Cheesner found 1 way to satisfy the puzzle. How many different ways are there to make all 12 clocks display 12:00?

There are twelve analog clocks (see this pic for image ) on a wall. The clocks are arranged evenly spaced in a circle. None of the clocks is running, however, they are linked in a quirky way. If we forward the time on any clock by x hours, the time on the two clocks on either side of the original clock will go forward by the same x hours. For instance, if the 3 consecutive clocks A, B, and C are currently displaying the time 1:00, 3:00, and 11:00, and we forward clock B by 2 hours, then clock A, B, and C will now display 3:00, 5:00, and 1:00. Let's say that starting from the very top clock and going clockwise, the clocks are currently displaying the times 4:00, 1:00, 1:00, 2:00, 3:00, 3:00, 4:00, 5:00, 5:00, 6:00, 7:00, 7:00. How much time should we add to each of the 12 clocks so that all 12 hour hands will point straight up, that is, all clocks show the time of precisely 12 o'clock?

I like your contributions to this board. Please don't worry about your english and continue to be a member of this board. As to how the chemist can escape death

Strategy and a general solution basis_vector.txt

Nice problem. There are less than half a million valid vectors out of 21000 possible binary vectors, which makes this problem very interesting indeed. Thanks for posting this, I enjoy it very much.

Thanks for posting that puzzle. I really enjoy working on it, as I do with all your puzzles. I approach it in the following manner:

Nice puzzle

Nice puzzle

My pleasure

Interesting puzzle. I really enjoy working on this. If I have to guess, I'd say that the root node is

I miss brainden. This isn't as optimal as I'd like, but it'll do for now.

I agree with this solution.

My impression here is that every prisoner increments the count by 1 during his visit. Every prisoner also keeps track of the count increase since his last visit. If any prisoner has a personal count that exceeds 100, he declares that everyone has been in the game. The issue that I see here is what if, by chance alone, the game only chooses 2 prisoners to enter the room repeatedly. Eventually one of them would falsely declare that everyone has been in the room.

Another possible answer

Dej Mar has the solution. Extra bonus points for the poem. Great work.

This is an improvement, but it could be even more optimal. It isn't clear from your solution what happens when a prisoner enters the room a second time. He is forced to modify 1 or 2 switches. Wouldn't that screw up the counting system for the next prisoner?

You're very close. It is possible to get more milage out of this methodology. The minimum number of needed visits to the room by the tallyman can be lower than 10.

This is an variation on the 100 prisoners and the light bulb. Suppose that there are 100 prisoners who are involved in a game. Each one of them has a chance to enter a room with five light switches. Each switch can be set to an OFF position or an ON position. The rules are as follows 1) The prisoners MUST flip either 1 or 2 switches of their choice during their turns. Flipping a switch here means changing the state of a light switch to the opposite of its current state. Not flipping anything during a turn is NOT an option. 2) They can not communicate to the other prisoners in ANY other fashion once the game starts. The prisoners are free to develop a strategy beforehand with knowledge of all these rules. 3) The prisoner chosen to enter the room at each turn is selected randomly from the pool of 100 prisoners with equal probability for each. 4) All 5 switches are initially in the OFF position, and this is KNOWN by all prisoners. 5) The time between visits is variable. If any prisoner can at any point correctly declare that ALL prisoners have been the the room, everyone wins. Otherwise they lose. Obviously this can be reduced to the original light-switch problem (e.g. use only 1 switch to communicate), but that would be vastly inefficient in that it would require many more visits than necessary to win the game. What is the optimal strategy to win the game? Optimal means the expected number of visits to win is smallest.

It is possible to take an infinity number of visits, but the chance of that happening approaching 0. Just like the chance of flipping an infinite number of heads in a row with a fair coin, it is possible but the chance of it happening is approaching 0. The average number of visits is how long it would take a typical game to win (not entirely correct definition, but it will do).

This is the answer. With the middle method above, my calculation shows that it takes an average of about 900 visits until a win, which is a vast improvement over the 99000 visits needed for the light-switch case. I suspect the improvement at the bottom at the above post can cut the expected number of visits down a couple hundred more. Great work, unreality.

I get

This is an variation on the 100 prisoners and the light bulb. Suppose that there are 100 prisoners who are involved in a game. Each one of them has a chance to enter a room with a digital calendar set on the month of July. The rules are as follows 1) The prisoners can set the digital calendar to any of 31 dates in July. They can not communicate to the other prisoners in ANY other fashion once the game starts. The prisoners are free to develop a strategy beforehand with knowledge of all these rules. 2) The prisoner chosen to enter the room at each turn is selected randomly from the pool of 100 prisoners with equal probability for each. 3) The initial setting of the clock is July 1st, and is KNOWN by all prisoners. 4) The time between visits is variable. If any prisoner can at any point declare that ALL prisoners have been the the room, everyone wins. Otherwise they lose. Obviously this can be reduced to the original light-switch problem (ie. July 1st is considered as OFF, July 2nd is considered as ON), but that would be vastly inefficient in that it would require many more visits than necessary to win the game. What is the optimal strategy to win the game? Optimal means the expected number of visits to win is smallest.