b***e
发帖数: 1419 | 1 In a dark room there is a rotating round table, with 4 symmetrically
located indistinguishable buttons. Each button can be either "on" or
"off", however inside the room one has no way to know what is the current
state. When the 4 buttons are all "on", and there is nobody inside, the
room is lighted.
The problem is as follows. A person is (repeatedly) allowed to enter the
room, and press whichever buttons he likes (that is, he can change the
states of more than one buttons). After he steps out, h | X****r
发帖数: 3557 | 2 Classify the button states into 4 classes:
0. all buttons are in the same state.
1. two diagonal buttons in one state and other two in the other
state.
2. two button on the same side in one state and other two in
the other state.
3. one button in one state and other three in the other state.
Obviously the above classification is rotation-invariant.
Define the following routines:
@. Do nothing and leave the room.
Push all buttons and leave the room.
This routine resolves state class 0
【在 b***e 的大作中提到】
: In a dark room there is a rotating round table, with 4 symmetrically
: located indistinguishable buttons. Each button can be either "on" or
: "off", however inside the room one has no way to know what is the current
: state. When the 4 buttons are all "on", and there is nobody inside, the
: room is lighted.
: The problem is as follows. A person is (repeatedly) allowed to enter the
: room, and press whichever buttons he likes (that is, he can change the
: states of more than one buttons). After he steps out, h
| b***e
发帖数: 1419 | 3 * Is there a solution that only pushes 2 buttons each time?
* Is there a solution that never pushes only 1 button?
* Is there a solution that is different from your solution?
* If so, are there infinitely # of solutions?
* Find the possibly shortest solution.
* Is there a solution for 5 buttons?
* Is there a solution for n buttons?
【在 X****r 的大作中提到】
: Classify the button states into 4 classes:
: 0. all buttons are in the same state.
: 1. two diagonal buttons in one state and other two in the other
: state.
: 2. two button on the same side in one state and other two in
: the other state.
: 3. one button in one state and other three in the other state.
: Obviously the above classification is rotation-invariant.
: Define the following routines:
: @. Do nothing and leave the room.
| t****t
发帖数: 6806 | 4 you mean 2 button max, right? otherwise 0001 is not solvable.
【在 b***e 的大作中提到】
: * Is there a solution that only pushes 2 buttons each time?
: * Is there a solution that never pushes only 1 button?
: * Is there a solution that is different from your solution?
: * If so, are there infinitely # of solutions?
: * Find the possibly shortest solution.
: * Is there a solution for 5 buttons?
: * Is there a solution for n buttons?
| b***e
发帖数: 1419 | 5 I do mean 2 buttons. So the answer is that this is not solvable. But you
raised another question:
* what initial states can be solved by pushing exactly 2 buttons each
time?
Basically, I know this is an ooooold problem (the first I saw it was in
1997, I guess), so I am not only looking for an answer but a generic model
that can help to understand and solve this whole class of problems, as
illustrated by my previous post.
【在 t****t 的大作中提到】
: you mean 2 button max, right? otherwise 0001 is not solvable.
| X****r
发帖数: 3557 | 6 I can't stop admiring people like you who have lots of energy to spend
on these interesting problems. Only if I were ten years younger. Wait
I take the last sentence back. Age is not an issue. Only if I never
played computer games ;-)
you
model
【在 b***e 的大作中提到】
: I do mean 2 buttons. So the answer is that this is not solvable. But you
: raised another question:
: * what initial states can be solved by pushing exactly 2 buttons each
: time?
: Basically, I know this is an ooooold problem (the first I saw it was in
: 1997, I guess), so I am not only looking for an answer but a generic model
: that can help to understand and solve this whole class of problems, as
: illustrated by my previous post.
| t****t
发帖数: 6806 | 7 this one, yes
pushing 1 button is equivalent to pushing 3 buttons then pushing all 4...
so yes there is a different solution
【在 b***e 的大作中提到】
: * Is there a solution that only pushes 2 buttons each time?
: * Is there a solution that never pushes only 1 button?
: * Is there a solution that is different from your solution?
: * If so, are there infinitely # of solutions?
: * Find the possibly shortest solution.
: * Is there a solution for 5 buttons?
: * Is there a solution for n buttons?
| b*****e
发帖数: 474 | 8 this problem reminds me of another one:
(in the beginning of the movie UHF): some one is setting on a bench
in a park playing a Rubik's cube with eyes closed. He kept asking the person
sitting next to him "is it done?" Well, in theory there is a way to do
this ...
【在 b***e 的大作中提到】
: In a dark room there is a rotating round table, with 4 symmetrically
: located indistinguishable buttons. Each button can be either "on" or
: "off", however inside the room one has no way to know what is the current
: state. When the 4 buttons are all "on", and there is nobody inside, the
: room is lighted.
: The problem is as follows. A person is (repeatedly) allowed to enter the
: room, and press whichever buttons he likes (that is, he can change the
: states of more than one buttons). After he steps out, h
| b*****e
发帖数: 474 | 9 我来尝试一下.
在桌子可以旋转的前提下, 按钮的状态可以分成六类
A. 1111 (都在ON) 这个自然最容易判断
B. 0000 也很容易判断, 四个按钮都按一遍, 就是状态A. 否则排除.
C. 0101 1010 这也很容易. 按两个不相邻的, 就变成 A/B. 也可排除.
D. 1001 1100 0110 0011. 按一次两个相邻的, 只可能变成A/B/C.
先做A/B 的判断, 都排除后可以肯定这时候是在状态 C. 这就也可排除了.
E. 1110 1101 1011 0111
F. 0001 0010 0100 1000
排除了 A/B/C/D 后那一定是 E/F 了, 就是有奇数个 1和0. 随便按一个,
就会回到 A/B/C/D. 那样的话, 也就可以按前面的方法, 达到状态 A.
【在 b***e 的大作中提到】
: In a dark room there is a rotating round table, with 4 symmetrically
: located indistinguishable buttons. Each button can be either "on" or
: "off", however inside the room one has no way to know what is the current
: state. When the 4 buttons are all "on", and there is nobody inside, the
: room is lighted.
: The problem is as follows. A person is (repeatedly) allowed to enter the
: room, and press whichever buttons he likes (that is, he can change the
: states of more than one buttons). After he steps out, h
| X****r
发帖数: 3557 | 10 Okay, insomnia bothers me, so I might as well look into this problem.
Say there is n buttons, their states being b_i, where 1 < i < n.
Now define the state of the buttons s = [b_1, ..., b_n]. However,
existence of rotation (or any other kind of operation) divides the
state set S into equivalence classes. Denote the set of these
equivalence classes S'. Similarly, define an action a = [f_1, ...,
f_n], where f_i, 1 < i < n, is whether the button is pushed or not;
and rotation divides the action set
【在 b***e 的大作中提到】
: I do mean 2 buttons. So the answer is that this is not solvable. But you
: raised another question:
: * what initial states can be solved by pushing exactly 2 buttons each
: time?
: Basically, I know this is an ooooold problem (the first I saw it was in
: 1997, I guess), so I am not only looking for an answer but a generic model
: that can help to understand and solve this whole class of problems, as
: illustrated by my previous post.
| b***e
发帖数: 1419 | 11 What would you do to the state
{[1,1,1,1], [1,0,0,0]}
with the transition of pushing 1 button only? | X****r
发帖数: 3557 | 12 I see what you're saying. The final state [1,...,1] should be removed
from S', and the power set P should include the empty set. We're
looking for a path from S' to the empty set.
【在 b***e 的大作中提到】
: What would you do to the state
: {[1,1,1,1], [1,0,0,0]}
: with the transition of pushing 1 button only?
| b***e
发帖数: 1419 | 13 Or, all 1 is going back to all 1 regardless of the operation.
Essentially, this is a FSA/regular expression problem.
It is trivial that when n=1 there's a solution.
It is easy that when n=2 there's a solution.
It is easy that when n is odd, there is no solution.
With some case study, we can see for any n>4, there's no solution.
So the only good case is when n is 1, 2 or 4.
To find the shortest solution, perform a BFS on the DFA.
【在 X****r 的大作中提到】
: I see what you're saying. The final state [1,...,1] should be removed
: from S', and the power set P should include the empty set. We're
: looking for a path from S' to the empty set.
|
|
