You are on a circular train, with carriages connecting so that they form a closed loop. There is a lightbulb in each carriage which is randomly set either on or off. You can find a switch to each lightbulb in the same carriage. You can only interact with switches and nothing else. You have infinite time, the train is not infinite but arbitrarily long. How do you determine, with 100% certainty, how many carriages are there in a loop?
I can do the following to check if the train’s length is a divisor of n. Remember the state of the lightbulb in the current carriage, then go n carriages forward and check if the state of the light is the same as remembered. If not, the train’s length is not a divisor of n. Otherwise, flip the light switch and go backwards n carriages, check the light. If it’s the same as remembered, the train’s length is not a divisor of n, otherwise it’s a divisor of n.
The overall algorithm is, for each n from 1 to infinity, perform the above steps and stop as soon as you encounter the first n such that the train’s length is a divisor of n. This n will be the train’s length.
I have a solution that involves moving back and forth across the loop. You pick a starting point, car 0, and move +1 car right and ensure the light is on, then go left to car −1 and ensure the light is off; then go to car +2: ON, car −2: off, etc.
The first time you travel more than half way around the loop, you’ll toggle a switch from the “other branch”, which you’ll then discover when you reverse. That will allow you to compute the total size of the loop.
You are on a circular train, with carriages connecting so that they form a closed loop. There is a lightbulb in each carriage which is randomly set either on or off. You can find a switch to each lightbulb in the same carriage. You can only interact with switches and nothing else. You have infinite time, the train is not infinite but arbitrarily long. How do you determine, with 100% certainty, how many carriages are there in a loop?
Solution:
I can do the following to check if the train’s length is a divisor of n. Remember the state of the lightbulb in the current carriage, then go n carriages forward and check if the state of the light is the same as remembered. If not, the train’s length is not a divisor of n. Otherwise, flip the light switch and go backwards n carriages, check the light. If it’s the same as remembered, the train’s length is not a divisor of n, otherwise it’s a divisor of n.
The overall algorithm is, for each n from 1 to infinity, perform the above steps and stop as soon as you encounter the first n such that the train’s length is a divisor of n. This n will be the train’s length.
Well done, however it’s one of the more convoluted correct answers that I’ve seen.
I have a solution that involves moving back and forth across the loop. You pick a starting point, car 0, and move +1 car right and ensure the light is on, then go left to car −1 and ensure the light is off; then go to car +2: ON, car −2: off, etc.
The first time you travel more than half way around the loop, you’ll toggle a switch from the “other branch”, which you’ll then discover when you reverse. That will allow you to compute the total size of the loop.
Break a switch and go counting the carriages until you see it again?
I guess it works with the riddle as formulated, but the true solution has to use the actual switch function.
If the dating partner solves it, then for extra credit, have them give a solution taking time proportional to the length of the loop.