Author |
Topic: Let There Be Circular Light. (Read 2984 times) |
|
rloginunix
Uberpuzzler
Posts: 1029
|
 |
Let There Be Circular Light.
« on: Mar 16th, 2014, 10:45am » |
 Quote  Modify
|
Let There Be Circular Light.
Once upon a time Uber Puzzler woke up hearing a disembodied voice from above:
- I am a disembodied voice from above. And you, Uber Puzzler, are deep in the underground bowls of Berkeley University in the Circle of Passage. The circle consists of N identical empty rooms connected to each other via corridors. Each room has a switch connected to an unreachable but clearly visible light. Flip the switch on and the light turns on. Flip the switch off and the light turns off.
- At first there was darkness ...
- Then, using my awesome powers of randomization, I turned the lights on in some rooms in a random pattern unknown to you.
- Using only the lights and their switches tell me the number of rooms in the Circle of Passage.
Some time later Uber Puzzler obtained correct N (in an eco-friendly way).
How did (s)he do it?
[edit]
Got rid of confusing "reasonable time" and O(N) in the problem statement.
[/edit]
|
| « Last Edit: Mar 17th, 2014, 7:12pm by rloginunix » |
 IP Logged |
|
|
|
gotit
Uberpuzzler
Gender: 
Posts: 804
|
|
Re: Let There Be Circular Light.
« Reply #1 on: Mar 16th, 2014, 10:57am » |
Quote Modify
|
First Pass: Turn off all the lights.
Second Pass: Turn on the lights and count the rooms until you reach a room that is already lighted.
You may ask how the Uber Puzzler knew that all the lights had been turned off. I would say (s)he did that by spending a reasonable amount of time going around the completely dark circle.
|
|
IP Logged |
All signatures are false.
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #2 on: Mar 16th, 2014, 11:16am » |
Quote Modify
|
If you read your first sentence carefully, "First Pass: Turn off all the lights", there is one word in it that introduces a contradiction.
Which word is it?
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: Let There Be Circular Light.
« Reply #3 on: Mar 16th, 2014, 11:28am » |
Quote Modify
|
Ok...You can't be sure that you have finished the first pass until you are sure that you have turned off all the lights...So I ll put it differently..
Spend reasonable amount of time going around the circle and turning off the lights until you are reasonably sure that all the lights are turned off...
|
| « Last Edit: Mar 16th, 2014, 11:29am by gotit » |
IP Logged |
All signatures are false.
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #4 on: Mar 16th, 2014, 12:00pm » |
Quote Modify
|
Please don't get me wrong - I'm just trying to steer you towards a correct solution.
1). The reason "reasonably sure" isn't going to work is because of the randomness of the on/off pattern which is not known ahead of time - it may very well so happen that while walking the Circle of Passage you will hit a number of dark rooms in a row that may make it look like you've turned off "all" the lights. But the algorithm is absolutely deterministic - it guarantees the room count with absolute certainty. No guessing and no luck is involved.
2). The problem statement "Some reasonable amount of time later ..." means that in a reasonable amount of time Uber Puzzler has found the algorithm first and obtained the actual N later. Sorry if I made it less clear than it should've been.
3). "All" in "all the lights are turned off" assumes the knowledge of N ahead of time, in which case there's no need to make any passes at all - just tell the disembodied voice from above the answer.
When you look at your drawings you have a bird's eye all-at-once wholesome view of the Circle of Passage and that affects your thinking. However, Uber Puzzler in the Circle of Passage doesn't have that view. (S)he doesn't know how many rooms are there.
[edit]
I've updated the problem statement to avoid the confusion. My apologies.
[/edit
|
| « Last Edit: Mar 16th, 2014, 12:16pm by rloginunix » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #5 on: Mar 16th, 2014, 12:19pm » |
Quote Modify
|
Start walking one way and make a pattern. I would choose some really difficult pattern, but since random is random, switching all lights on is also good enough (btw. why would someone try to swith OFF all the lights, when you can switch ON all of them - much more friendly).
When you already suspect that you reached the starting point, switch one lamp off and go the other way. If after n steps you find a light switch off, it was indeed the one you switched off. If is still on, then it was a misleading repetition of pattern, so you need to continue again.
I am not sure it is O(N), but so far the best I can think of.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #6 on: Mar 16th, 2014, 12:40pm » |
Quote Modify
|
jollytall, I think you started seeing the light ...
Again, my apologies, guys. Wording and typing problems is hard. God knows I'm trying. O(n) is not the first degree polynomial. It's just a notation. An asymptotic behavior of some yet unknown function of the number of rooms when that number is large.
jollytall, "really difficult pattern" may very well coincide with the random one chosen by the disembodied voice from above. Also, in "switching all the lights on" the word "all" is the problem. If "all" is known then just give it as the answer.
But your answer does contain a portion of the algorithm. Be more specific.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #7 on: Mar 16th, 2014, 1:39pm » |
Quote Modify
|
This is why I wrote all ON is as good as a complex pattern.
All means all I have visited.
e.g. I switched on 500 lamps and then I see a sequence of on more than another let`s say 1000 on then I switch one off and turn back. I should find it in more than 500 steps but less than 1500. If I need to go back more than 1500 then it is not a real finding, so I can do it again (using these 1500 steps as the starting).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Let There Be Circular Light.
« Reply #8 on: Mar 16th, 2014, 1:46pm » |
Quote Modify
|
I don't see what the problem with Jollytall's solution is
You turn on some improbable pattern of lights (like, turn everything on that you encounter), and walk/count till you find a place that looks like the start of your pattern.
Change the (suspected) start in an identifiable way, and walk back as many lights as you've counted. If the (actual) start has changed then you've got the right count.
Otherwise, walk back to the not-actually-the-start-of-your-pattern, and continue walking/counting while continuing your pattern.
Rinse&repeat till you achieve a glossy shine.
[e]I wish I could write faster[/e]
|
| « Last Edit: Mar 16th, 2014, 1:48pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #9 on: Mar 16th, 2014, 2:16pm » |
Quote Modify
|
You, guys, are getting closer and closer. I just have to guide you carefully towards the intended solution.
OK, let's see. "Improbable" still involves a degree of luck. If Uber Puzzler's plan is to turn all the encountered lights on then what if all the lights are on to begin with? Uber Puzzler doesn't know the pattern ahead of time. If the plan is to turn all the lights off then may be they are all off to begin with.
The algorithm should consist of some number of statements that work no matter what N and the initial on/off pattern is. Step 1, step 2, step 3, ...
Uber Puzzler doesn't know that, but let's assume we do. There are 5 rooms in the Circle of Passage and the lights in all of them are initially on. According to jollytall's algorithm we do 100 circles to make sure we count 500 lights that are on. What should we do next?
[edit]
Addition: "and the initial on/off pattern".
[/edit]
|
| « Last Edit: Mar 16th, 2014, 2:35pm by rloginunix » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #10 on: Mar 16th, 2014, 2:48pm » |
Quote Modify
|
why would I make 100 rounds? If after 5 rooms (where I had to switch on few) I see a sufficiently long pattern (I would go another 10) I would turn back already.
You might want to turn back immediately when you have the right to think that you are around. That is as soon as you have one unvisited on. It might be a bit zig-zaggy, why I would wait a bit more.
Interesting question if the initial state is really random, what is the optimal number of ONs before turning back.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #11 on: Mar 16th, 2014, 3:41pm » |
Quote Modify
|
on Mar 16th, 2014, 2:48pm, jollytall wrote:| why would I make 100 rounds? |
|
I'm just trying to steer you towards framing your good observations into a working algorithm. Earlier you said 500 - I used 500. Now you are saying "If after 5 rooms ...". I will use 5. Say, there are 3 rooms in the Circle of Passage ... Problem is Uber Puzzler, boots on the ground, doesn't know there are 5 rooms in the Circle of Passage. (S)he needs to find it.
You are almost there. One of your sentences is dead on. You've hit the nail on the head: "You might want to turn back immediately when you have the right to think that you are around".
Try putting your solution down as a working algorithm that we can apply to any N and any, truly random, initial distribution of lights. The actual algorithm works exactly that way - no assumptions.
So (for a hypothetical example):
Step 1. Walk 5(?) rooms in a given direction. For each room: if light is off then turn it on.
Step 2.
...
|
| « Last Edit: Mar 17th, 2014, 7:22pm by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #12 on: Mar 16th, 2014, 4:14pm » |
Quote Modify
|
Some snippets of my search. I went through roughly the same motions as you guys (it just took me longer). When I realized nothing is working I said "forget it. Let me see if I can solve this problem if there is only 1 room in the Circle of Passage. What do I have to do to make sure that I can with absolute certainty say that yes, I am back in the room #1 and not the second room of a 2-room circle that happened to have the same state of the light? Once I cleared that up I moved on to a 2-room circle. How can I be sure that I am back in the anchor room of a 2-room circle and not the 3-rd room of a 3-room circle which happened to have the same state of the light? By the time I did that with a 4-room circle I started seeing the light.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #13 on: Mar 16th, 2014, 6:04pm » |
Quote Modify
|
OK, how about this.
If we define "one step" or just "step" as a walk from one room to the next then could you express the number of such steps your algorithm takes in terms of the total number of rooms in the worst case - for consistency sake. Worst case means that all the lights are always in the least convenient state and you always have to do something with them. The algorithm should of course work in the non-worst case scenario just the same, perhaps taking less steps.
Basically, formalize your algorithm. For an arbitrary integer n come up with a worst case function S(n) which can be used to calculate (without actually walking) the number of steps for any m != n. So that when we plug an arbitrary room count into the function we get the actual worst case step count. Using totally made up, off the wall, not real numbers for demonstration purposes: S(1) = ... = 1, S(2) = ... = 2, S(3) = ... = 3, and so on.
If you try doing that I think you'll see what I mean.
[edit]
Also, guys, don't forget about the hint built into the problem statement: "(in an eco-friendly way)". When it comes to light bulbs which one of its two states is eco-friendly?
[edit]
|
| « Last Edit: Mar 16th, 2014, 9:40pm by rloginunix » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #14 on: Mar 16th, 2014, 10:51pm » |
Quote Modify
|
I think you missed my point. You can always do the turning back "immediately" logic. E.g. go right 1 OFF, so SWITCH to ON. Next one to the right ON, so you assume you are already back, i.e. TURN OFF and go backwords. Room 1 disappointment, because still ON. Continue left. Next room (the n-th) is OFF. So now you are potentially happy (and turn ON), but not sure. Make one more to the left (n-1). DIsappointment, because that is still OFF (so turn ON again) and continue. NExt one (n-2) is ON. Now you are really happy thinking n-1=2 and n-2=1. So you turn it OFF and go backwords. And so on.
If n is really large, then you have a lot of turning back. Worst case you turn back every room (Think a ring where you are in the 1st and the sequence is (oFf and oN):
FNNNNNNNN.....NNNNNNNNF.
The total number is in the range of n2/2, what is not O(N).
This is why I wrote earlier to use a longer reassuring sequence (e.g. twice the thought - meaning first suspcted - ring length).
It is a nice question to assume the optimal length of the reassuring pattern in case of a total random starting state.
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: Let There Be Circular Light.
« Reply #15 on: Mar 17th, 2014, 12:15am » |
Quote Modify
|
on Mar 16th, 2014, 4:14pm, rloginunix wrote:| Some snippets of my search. I went through roughly the same motions as you guys (it just took me longer). When I realized nothing is working I said "forget it. Let me see if I can solve this problem if there is only 1 room in the Circle of Passage. What do I have to do to make sure that I can with absolute certainty say that yes, I am back in the room #1 and not the second room of a 2-room circle that happened to have the same state of the light? Once I cleared that up I moved on to a 2-room circle. How can I be sure that I am back in the anchor room of a 2-room circle and not the 3-rd room of a 3-room circle which happened to have the same state of the light? By the time I did that with a 4-room circle I started seeing the light. |
|
For 1 room:
Room 1 : TURN ON if OFF.
Go To ROOM 2, which is actually ROOM 1.
TURN OFF (it will definitely be ON).
GO BACK to the previous room.
If it's on, there are more than 1 rooms. Else there is only 1 room.
For 2 Rooms.
Room 1 : TURN ON if OFF.
Go To ROOM 2.
TURN OFF if ON.
GO BACK to the previous room (ROOM 1).
It will be definitely ON. So there are at least 2 Rooms.
Go to room 3 (which is actually ROOM 1)
Turn OFF (it will definitely be on).
Go Back 2 rooms. If it is OFF, there are 2 rooms. Else there are at least 3 rooms.
|
|
IP Logged |
All signatures are false.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Let There Be Circular Light.
« Reply #16 on: Mar 17th, 2014, 12:17am » |
Quote Modify
|
You can avoid turning back at every room in the worst case, by doubling or tripling (or ntupling) the range of rooms you explore each iteration. (Although it's quite improbably you'd need to if the initial pattern is random.)
How about:
* go right X rooms turning the lights off
* turn the last light on
* go X rooms left (stumbling in the dark, cursing under your breath),
** if you encounter a light that's on, then you know you've gone gone a full circle, and how long that circle is.
** otherwise go 2X+1 rooms further left while turning lights off; set X=3X, swap(left,right), goto 2.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: Let There Be Circular Light.
« Reply #17 on: Mar 17th, 2014, 12:23am » |
Quote Modify
|
In General
Turn ON Room 1.
Go ahead until you find another room with light ON. Let's say you find it after k Steps.
Turn if Off.
Go back k steps to Room 1. If it is ON, there are at least k rooms. Else there are k rooms.
Next, move ahead until you find a lighted room (say m > k).
Turn off and move back m steps to room1.
If it is off, there are m rooms. Else there are at least m rooms.
Continue till you find n
|
| « Last Edit: Mar 17th, 2014, 12:29am by gotit » |
IP Logged |
All signatures are false.
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #18 on: Mar 17th, 2014, 12:46am » |
Quote Modify
|
As my son has just pointed out; my above zig-zag strategy is not even the most aggressive, it already had an element of optimisation (confirmation) in it. When after 1 and 2 and turning back I reach the n-th (and find it OFF), then I might already think that that is the 2nd and without validating that n-1=1 or not, can turn it ON and going back to check number 2 (whether it became ON from the last OFF).
In the worst case scenario it is still O(n2), the only difference is that the worst pattern is:
FNNNNNN .... FFFFFFFF. (Right the token lamp is ON, left it is OFF).
Regarding the optimal solution, I still think that the immediate turn back is far from optimal. The zig-zag is essentially walking one suspected ring and as soon as it can be a ring (without any more confirmation) turn back and validate the ring.
My recent one had at least one more confirming step (to n-1) in it, filtering out when n-1 was also OFF.
My gut feel tells me that at least one confirming ring would make sense. If it is finally the real ring then I make n extra steps (i.e. the last steps are not n+n, but n+N+n), but save a lot of zig-zaging. Imagine a 100 long ring. In the zig-zag logic, I would make randomly about 50 turn backs (n2/4 steps), worst case n2/2. In the new logic, even if the original distribution is the worst possible, I make steps about 1+3+7+15+31+...+100+100+100 bringing the total number of steps down to O(N) (about 3*N).
The real question to me now, whether one full or only half or (as I originally suggested) two full confirming cycles are used in the optimal case if the initial distribution is random and n is large. As N turns large, we might reduce the confirmation ring to less than a full ring. E.g. In case of N=100, we might turn back after let's say 20 confirmation steps, leaving a one per million chance that we made it early.
The same question for the worst initial distribution.
Edit: I started to write like an hour earlier, but could not push "Post". So sorry for some elements of duplication.
|
| « Last Edit: Mar 17th, 2014, 12:50am by jollytall » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #19 on: Mar 17th, 2014, 7:13am » |
Quote Modify
|
Good morning, guys. I just woke up and need to go buy some milk for my coffee so that I can think straight.
You basically got it. Didn't have the time (but I will) to analyze your latest answers in all the details but I feel that "gotit" got it closest to what I had in mind. I would put the algorithm thus:
Step 1. Pick a room, any room.
Call it a Marker room.
If the light in the Marker room is off then turn it on.
Pick a direction, any direction - say, clockwise.
Set RoomsVisited = 0.
Step 2. Go clockwise into the next room.
Step 3. Got there.
Increment RoomsVisited by 1.
Step 4. If the light in that room is on then
{
turn it off and
walk back RoomsVisited corridors (steps).
This will put you back into the Marker room.
If the light in the Marker room is off then
{
you turned it off RoomsVisited steps ago
which means you've made full circle and
You are done: RoomsVisited is the answer.
}
else
/* Didn't make the full circle yet. Start all over again. */
Set RoomsVisited = 0
go to step 2.
}
else
{
/* The light in the current room is off - keep going. */
go to Step 2.
}
Sorry for the small text. I'm going blind trying to read it myself. Not sure how to make it bigger.
Anyway, above algorithm works for any however random initial distribution of light states.
By the end of this procedure all the lights will be off which is eco-friendly. The process is symmetrical in reference to the state of the light - you will get the same answer if you flip the states to their opposites in the algorithm above. If you keep the light in the Marker room off then in the next room you will turn the light on if it's off. By the end of this process all the lights will be on. Not very eco-friendly.
To come up with a formula for the worst case scenario we can do some small number of pen and paper calculations for 1, 2, 3, and 4-room circles. I numbered the rooms in the clockwise fashion. Marker room is always at 12 o'clock and I numbered it as 1. The number in parenthesis is the number of times that room is visited:
1-room circle: 1(2) = 2
2-room circle: 1(3) + 2(3) = 3 + 3 = 1 + 2 + 3 = (1 + 3 ) + 2 = 6
3-room circle: 1(4) + 2(5) + 3(3) = 4 + 5 + 3 = 1 + 3 + 5 + 3 = (1 + 3 + 5) + 3
4-room circle: 1(5) + 2(7) + 3(5) + 4(3) = 5 + 7 + 5 + 3 = (1 + 3 + 5 + 7 ) + 4
You can see that the pattern emerges: S(N) = N^2 + N = N*(N + 1) since the sum of first N odd integers is N^2. Then we get worst case O(n) = N^2.
Please let me go do my morning routine and I will be back to think about towr's and jollytall's replies in depth.
[edit]
Made the algorithm's text size bigger. Thank you, towr.
[/edit]
|
| « Last Edit: Mar 18th, 2014, 8:27am by rloginunix » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Let There Be Circular Light.
« Reply #20 on: Mar 17th, 2014, 8:51am » |
Quote Modify
|
on Mar 17th, 2014, 7:13am, rloginunix wrote:| Sorry for the small text. I'm going blind trying to read it myself. Not sure how to make it bigger. |
|
You can use the size tag.
Quote:| You can see that the pattern emerges: S(N) = N^2 + N = N*(N + 1) since the sum of first N odd integers is N^2. Then we get worst case O(n) = N^2. |
|
That's rather inefficient. You can get a linear run-time.
And I don't quite understand the way you're using O(n); big-O notation has a meaning that doesn't fit your usage.
|
| « Last Edit: Mar 17th, 2014, 8:54am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #21 on: Mar 17th, 2014, 10:43am » |
Quote Modify
|
Want to clear one thing up real quick. I hope I didn't offend anyone with my replies. I've never done this before and I'm not trying to torture anyone. The goal of my replies is to make sure you derive the same pleasure from your deductions as I do. If you don't like something in my style - let me know, I will adapt.
on Mar 17th, 2014, 8:51am, towr wrote:
And I don't quite understand the way you're using O(n); big-O notation has a meaning that doesn't fit your usage. |
|
Yes, I'm an idiot. I confused myself and everyone else. Problem is I'm not sure what to put down as a question: "find the big oh", "find the asymptotic behavior of your function when the argument tends to positive infinity"? What's the best short and sweet that will not confuse anyone and convey the correct meaning?
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #22 on: Mar 17th, 2014, 10:44am » |
Quote Modify
|
jollytall, I've looked at your algorithm. I think all in all it's almost the same but I have a couple of questions.
on Mar 16th, 2014, 10:51pm, jollytall wrote:| I think you missed my point. You can always do the turning back "immediately" logic. E.g. go right 1 OFF, so SWITCH to ON. Next one to the right ON, so you assume you are already back, i.e. TURN OFF and go backwords. Room 1 disappointment, because still ON. Continue left. Next room (the n-th) is OFF. So now you are potentially happy (and turn ON), but not sure. Make one more to the left (n-1). DIsappointment, because that is still OFF (so turn ON again) and continue. NExt one (n-2) is ON. Now you are really happy thinking n-1=2 and n-2=1. So you turn it OFF and go backwords. And so on. |
|
Trying to put it in an algorithmic way for, say, a 3-room circle. Stars are rooms with the room numbers next to them:
*1
*3 *2
When you say "go right" - right relative to what? I'm assuming a marker room. What is the state of light in the marker room? I'm assuming you make sure it's off. Step right once - we are in room 2. If light in room 2 is off - switch it on and move on. Step right once more - we are in room 3. If light in room 3 is on then turn it off and step back once - we are in room 2, light is on. Step back once more - we are in the marker room, room 1. Light is off here. Turn it back on. Done. Now the state of lights is: 1 - on, 2 - on, 3 - off. Next. Step left once - we are in room 3. Light is off here. Turn it on. State: 1 - on, 2 - on, 3 - on. Step left (?) once - we in room 2. Light is on here. Turn it off ...
I see what you are trying to do. All in all you are correct but I think you are overshooting once you reach the marker room and trying to step left. At what point do we stop?
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #23 on: Mar 17th, 2014, 10:46am » |
Quote Modify
|
towr, I've looked at your suggestion:
on Mar 17th, 2014, 12:17am, towr wrote:How about:
* go right X rooms turning the lights off
* turn the last light on
* go X rooms left (stumbling in the dark, cursing under your breath),
** if you encounter a light that's on, then you know you've gone gone a full circle, and how long that circle is.
** otherwise go 2X+1 rooms further left while turning lights off; set X=3X, swap(left,right), goto 2. |
|
Your overall idea is also correct. But I think turning the light on in the X-th room will make it difficult distinguishing it from the marker room.
Using a 5-room configuration let's fix X at 2. From the marker room we step right once - turn the light off in room 2, step right once more - we are in room 3. Turn the light on in room 3. Step back twice - we are in the marker room where the light is on or off? Not sure. Let's say it's on. If I read your algorithm correctly you're saying we've made full circle if that light is on but we've visited only 3 rooms so far. Also, how do we choose the value of X?
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #24 on: Mar 17th, 2014, 11:42am » |
Quote Modify
|
Here is how I did my worst case counts. 3-room circle. Initially all the lights are on (worst case for this scheme):
In the marker room, light is on. Step right once. Room 2, turn light off, set visits = 1. Step back once. Marker room, set visits = 1. Light is on - not done yet.
Step right once. Room 2, light is off, visits = 2. Step right once. Room 3, turn light off, visits = 1. Step back once. Room 2, visits = 3. Step back once. Marker room, visits = 2. Light is on - not done yet.
Step right once. Room 2, visits = 4. Step right once. Room 3, visits = 2. Step right once. Marker room, turn light off, visits = 3. Step left once. Room 3, visits = 3. Step left once. Room 2, visits = 5. Step left once. Marker room, visits = 4. Light is off - we are done. Total number of visits (or steps):
S(3) = 1(4) + 2(5) + 3(3) = 12
It's tedious but you see exactly what's going on with the steps or visits to each room as the count progresses.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print