train wagons

[poochon]

well, i'll be damned (and honored)... first one to post a riddle here, ever ^^

so, there's a circle of an unknown number of train wagons. in every wagon there's a light bulb and a switch, and the initial state (on/off) is unknown. you are in one of the wagons. how can you find the number of wagons using only the light bulbs (and not anything obvious like writing your name on the wall of the first or something)? you can use the switches as you like.

[Zapp]

well, if you take it literally, then there are unlimited wagons.
assume each wagon is a side of a polygon.
because they are aligned in a circle you would need infinite sides (therefore infinite wagons) to fulfill that requirement which leads to the conclusion, that only chuck norris is able to count the wagons

even if the number of wagons is not infinite and you start walking around an turn the lights on and off with a certain pattern, you cannot be certain that you have gone in a full circle.

maybe you can use some trigonometry. you could choose a series of trains (for example 5 in a row, 1 3 and 5 are lit, 2 and 4 are not) with that you could construct a line on which the center of the circle has to be. I think with the angles you could calculate how many cars there are in the circle with the triangles angles.
let's assume we have a triangle which has the diameter as baseline and has it's corners on the circle. that triangle must be a right triangle with the angles 45° 45° and 90°. now put the constructed triangle and the assumed right triangle in an equation, together with the five trains, and you should be able to solve that into the 1/2 of the trains. multiply that by 2 and voilá

[SpikedMath]

well, if you take it literally, then there are unlimited wagons.
assume each wagon is a side of a polygon.
because they are aligned in a circle you would need infinite sides (therefore infinite wagons) to fulfill that requirement

I think poochon means that you have a fixed number of wagons (say n) and your goal is to determine what n is. Somehow you have to use the light switches while traveling from wagon to wagon (where the wagons are connected in a circle).

[poochon]

well, you know what i meant :\
#define circle polygon
-or-
assume the wagons are curved and not straight

well, if you take it literally, then there are unlimited wagons.
assume each wagon is a side of a polygon.
because they are aligned in a circle you would need infinite sides (therefore infinite wagons) to fulfill that requirement

I think poochon means that you have a fixed number of wagons (say n) and your goal is to determine what n is. Somehow you have to use the light switches while traveling from wagon to wagon (where the wagons are connected in a circle).

yes, exactly.

[ironclaw]

Here's a solution.

Spoiler! :

Name the wagon you start in wagon 1, and name the wagons consecutively from 1 to n. Turn off the light in wagon 1, and execute the following loop:

Suppose that you are in wagon i. Go to wagon i+1. If the light is on, go on to the next wagon, and repeat this loop. If the light is off, turn it on and go back to wagon 1. If the light is on at wagon 1, then there are exactly i wagons. Otherwise, if the light is off at wagon 1, go to wagon i+1 and repeat this loop.

[Zapp]

I have found a solution, but I am not able to express it properly, I have edited my first post with that solution, I hope you understand what I am trying to say in that post. I lack the mathematical terminology, because english is not my native language

[bmonk]

Assuming that the number of wagons is a reasonably small number, such that you can check out the light in each, and move on to the next one, and make it back to the original wagon in, say, five or ten minutes--and nobody else is messing with the lights, then:

Find a light that is on, and switch it off. Count wagons, checking the lights that are off to see if they are still warm. When you get to the off-but-warm light, you've made a complete circle.

[poochon]

Here's a solution.

Name the wagon you start in wagon 1, and name the wagons consecutively from 1 to n. Turn off the light in wagon 1, and execute the following loop:

Suppose that you are in wagon i. Go to wagon i+1. If the light is on, go on to the next wagon, and repeat this loop. If the light is off, turn it on and go back to wagon 1. If the light is on at wagon 1, then there are exactly i wagons. Otherwise, if the light is off at wagon 1, go to wagon i+1 and repeat this loop.

NICE! that's the solution i've been looking for

zapp and bmonk, in the solution you had to use only the lights

[bmonk]

Here's a solution.

Name the wagon you start in wagon 1, and name the wagons consecutively from 1 to n. Turn off the light in wagon 1, and execute the following loop:

Suppose that you are in wagon i. Go to wagon i+1. If the light is on, go on to the next wagon, and repeat this loop. If the light is off, turn it on and go back to wagon 1. If the light is on at wagon 1, then there are exactly i wagons. Otherwise, if the light is off at wagon 1, go to wagon i+1 and repeat this loop.

NICE! that's the solution i've been looking for

zapp and bmonk, in the solution you had to use only the lights

I thought I did--but I did have more constraints on the situation. And I finessed a "third" state--recently turned off--to get a unique marker.

[Zapp]

oh, I thought you could look outside the window to construct the triangles

[SpikedMath]

Here's a solution.

Name the wagon you start in wagon 1, and name the wagons consecutively from 1 to n. Turn off the light in wagon 1, and execute the following loop:

Suppose that you are in wagon i. Go to wagon i+1. If the light is on, go on to the next wagon, and repeat this loop. If the light is off, turn it on and go back to wagon 1. If the light is on at wagon 1, then there are exactly i wagons. Otherwise, if the light is off at wagon 1, go to wagon i+1 and repeat this loop.

This is a nice solution! It might take a long time to do if you have to return to wagon 1 all the time. I wonder if there is a shorter solution? Hmm...

[capncanuck]

I wonder if there is a shorter solution? Hmm...

Well, it's simple enough to program.

[poochon]

bmonk- well, yea, that's what i meant- no new states

[TalksToRainbows]

Well, it's simple enough to program.

I did

Java code here, if any one wants to run it (sorry it's not commented):

Spoiler! :

Code: Select all

import java.util.Random;

public class Wagons
{
   private static Random gen = new Random();
   private static int nWagon;
   private static boolean[] lightState;
   private static int n;
   private static int i;
   
   public static void main(String args[])
   {
      nWagon = gen.nextInt(100) + 1;
      System.out.printf("(There are %d wagons, but shh, I haven't worked it out yet!)%n", nWagon);
      
      lightState = new boolean[nWagon+1];
      
      for(int t = 1; t <= nWagon; t++)
      {
         int next = gen.nextInt(1);
         if(next == 1)
         {
            lightState[t] = true;
         }
         else
         {
            lightState[t] = false;
         }
      }
      
      i = 1;
      n = 1;
      lightState[i] = false;
      boolean loop = true;
      while(loop)
      {
         nextN();
         i++;
         if(!lightState[n])
         {
            lightState[n] = true;
            if(lightState[1])
            {
               loop = false;
            }
         }
      }
      
      System.out.printf("I think there are %d wagons%n", i-1);
      if(i-1 == nWagon)
      {
         System.out.printf("Yay! I was right!%n");
      }
      else
      {
         System.out.printf("Damn, I'm wrong.%n");
      }
   }
   
   public static void nextN()
   {
      n++;
      if (n == nWagon+1)
      {
         n = 1;
      }
   }
   
   public static void prevN()
   {
      n--;
      if (n == 0)
      {
         n = nWagon;
      }
   }
}

[hellerbarde]

aren't you allowed to look outside the windows? that might make it easier... but only for a number of wagons so that you could still see the other side of the circle

[Zapp]

aren't you allowed to look outside the windows? that might make it easier... but only for a number of wagons so that you could still see the other side of the circle

no we are not allowed to look out of the window, which renders my solution useless ^^

[ironclaw]

This is a nice solution! It might take a long time to do if you have to return to wagon 1 all the time. I wonder if there is a shorter solution? Hmm...

Here's an outline of a potentially faster solution.

Spoiler! :

Go through the wagons and set the lights to an alternating pattern (that is, on off on off etc.). When you get back to an alternating pattern, you know that you may have gone around the loop once. Then the strategy differs depending on whether there is an odd or even number of wagons.

If there is an odd number of wagons, you will automatically switch the parity of the alternating pattern as you go through the second time, so you just have to backtrack and check if there is indeed a break in the alternating pattern.

If there is an even number of wagons, then you will have to manually disrupt the alternating pattern at a wagon and backtrack to check if there is a disruption in the pattern.

In either case, if you find that there is a break or disruption in the alternating pattern, you can figure out the number of wagons. However, if not, then you can continue without having to go back to where you were - just go on in the opposite direction to your original direction. This way, you don't have to go forwards and backwards too much.

[xander]

This is a nice solution! It might take a long time to do if you have to return to wagon 1 all the time. I wonder if there is a shorter solution? Hmm...

Here's an outline of a potentially faster solution.

Spoiler! :

Go through the wagons and set the lights to an alternating pattern (that is, on off on off etc.). When you get back to an alternating pattern, you know that you may have gone around the loop once. Then the strategy differs depending on whether there is an odd or even number of wagons.

If there is an odd number of wagons, you will automatically switch the parity of the alternating pattern as you go through the second time, so you just have to backtrack and check if there is indeed a break in the alternating pattern.

If there is an even number of wagons, then you will have to manually disrupt the alternating pattern at a wagon and backtrack to check if there is a disruption in the pattern.

In either case, if you find that there is a break or disruption in the alternating pattern, you can figure out the number of wagons. However, if not, then you can continue without having to go back to where you were - just go on in the opposite direction to your original direction. This way, you don't have to go forwards and backwards too much.

Spoiler! :

What if the lights are initially in an alternating pattern? What if the first n lights are not, but the last m are?

xander

[Zapp]

Here's an outline of a potentially faster solution.

Spoiler! :

Go through the wagons and set the lights to an alternating pattern (that is, on off on off etc.). When you get back to an alternating pattern, you know that you may have gone around the loop once. Then the strategy differs depending on whether there is an odd or even number of wagons.

If there is an odd number of wagons, you will automatically switch the parity of the alternating pattern as you go through the second time, so you just have to backtrack and check if there is indeed a break in the alternating pattern.

If there is an even number of wagons, then you will have to manually disrupt the alternating pattern at a wagon and backtrack to check if there is a disruption in the pattern.

In either case, if you find that there is a break or disruption in the alternating pattern, you can figure out the number of wagons. However, if not, then you can continue without having to go back to where you were - just go on in the opposite direction to your original direction. This way, you don't have to go forwards and backwards too much.

Spoiler! :

What if the lights are initially in an alternating pattern? What if the first n lights are not, but the last m are?

xander

Spoiler! :

if it is initially alternating, proceed with the first solution.

in the second case disrupt the pattern at m and go back to the beginning. if the pattern is disrupted, then you have m trains

[xander]

Here's an outline of a potentially faster solution.

Spoiler! :

Go through the wagons and set the lights to an alternating pattern (that is, on off on off etc.). When you get back to an alternating pattern, you know that you may have gone around the loop once. Then the strategy differs depending on whether there is an odd or even number of wagons.

If there is an odd number of wagons, you will automatically switch the parity of the alternating pattern as you go through the second time, so you just have to backtrack and check if there is indeed a break in the alternating pattern.

If there is an even number of wagons, then you will have to manually disrupt the alternating pattern at a wagon and backtrack to check if there is a disruption in the pattern.

In either case, if you find that there is a break or disruption in the alternating pattern, you can figure out the number of wagons. However, if not, then you can continue without having to go back to where you were - just go on in the opposite direction to your original direction. This way, you don't have to go forwards and backwards too much.

Spoiler! :

What if the lights are initially in an alternating pattern? What if the first n lights are not, but the last m are?

xander

Spoiler! :

if it is initially alternating, proceed with the first solution.

in the second case disrupt the pattern at m and go back to the beginning. if the pattern is disrupted, then you have m trains

You proposed solution depends upon being able to create a sequence of lights that you can recognize. Unfortunately, you cannot create such a sequence, as it could occur at random. Given a long enough train of wagons, any sequence of lights that are on and off could occur. How do you know that you are at the beginning of your sequence, rather than the beginning of a sequence that occurs later in the wagon train that looks like your sequence by random happenstance?

As an example, suppose that the train has 10 wagons in it, and the initial pattern of lights is 0000101010 (0 for off, 1 for on). You start by turning on the first light. You get to the fifth light, and your pattern starts again. How do you know that you are not at the beginning?

xander