A bit in bottles [concise statement]
Francois Grieu
a number of bottles, initially empty, under these constraints:
- any two readings of the bit must be identical unless a change
of the bit was decided in between;
- we can get interrupted at *ANY* time;
- we can order to "empty" or "fill" a bottle; either can be
interrupted, which can leave the bottle neither empty nor full;
- we must not fill a bottle that is not empty;
- the information we get on bottles is only a vector of bits, one
per bottle, 0 for "not full" and 1 for "not empty"; the value
obtained for bottles neither empty nor full is arbitrary, and
in particular can change after an interruption.
Is it possible? Give a proof.
Francois Grieu
Verbose statement: <4b661c25$0$10143$426a...@news.free.fr>
http://groups.google.com/group/rec.puzzles/msg/01e6d2922423bf4c
Nick Wedd
<fgr...@gmail.com> writes
Thank you. I am almost sure that I now understand the puzzle correctly.
My immediate impression was that it must be impossible. I now think
that there may be a solution, and if there is it must involve at least
four bottles.
Nick
--
Nick Wedd ni...@maproom.co.uk
Francois Grieu
> My immediate impression was that it must be impossible. I now think
> that there may be a solution, and if there is it must involve at least
> four bottles.
Very partial spoiler: if there is a solution with two bottles,
then I'll stop attempting anything harder than sudoku.
Francois Grieu
James Dow Allen
I just glanced at this. But it seems like there are at least
two major differences from the original problem.
On Feb 2, 7:08 pm, Francois Grieu <fgr...@gmail.com> wrote:
> We shall store a bit of information
In the old problem, normal operation was
Red -> Off -> Green -> Off -> Red -> ...
and the Red/Green bit was *not* required to be stored
reliably if interrupted during "Off." Or so I thought.
> - any two readings of the bit must be identical unless a change
> of the bit was decided in between;
In the old problem, a bottle at an intermediate (interrupted)
state could read out Empty and then, after restart, Full
(or vice versa) even though it wasn't operated on. Or so
I thought.
I *think* I've found a 6-bottle solution for the old
problem, but will post it in the old thread, since this
seems to be a new problem.
James Dow Allen
Francois Grieu
> I just glanced at this. But it seems like there are at least
> two major differences from the original problem.
That would be my failure.
> On Feb 2, 7:08 pm, Francois Grieu <fgr...@gmail.com> wrote:
>
>> We shall store a bit of information
>
> In the old problem, normal operation was
> Red -> Off -> Green -> Off -> Red -> ...
> and the Red/Green bit was *not* required to be stored
> reliably if interrupted during "Off." Or so I thought.
Any solution for the concise statement gives a solution
for the verbose statement, as follows:
- read the bit
- light Green or Red accordingly
- wait a second
- turn light off
- toggle bit
- repeat.
Without detailed proof yet, I conjecture that the reverse applies.
>> - any two readings of the bit must be identical unless a change
>> of the bit was decided in between;
Here "bit" refers to the bit to be implemented using the
bottles.
> In the old problem, a bottle at an intermediate (interrupted)
> state could read out Empty and then, after restart, Full
> (or vice versa) even though it wasn't operated on. Or so
> I thought.
That's still the case.
" the value
obtained for bottles neither empty nor full is arbitrary, and
in particular can change after an interruption. ".
>
> I *think* I've found a 6-bottle solution for the old
> problem, but will post it in the old thread, since this
> seems to be a new problem.
>
> James Dow Allen
Francois Grieu
Francois Grieu
> Any solution for the concise statement gives a solution
> for the verbose statement, as follows:
> - read the bit
> - light Green or Red accordingly
> - wait a second
> - turn light off
> - toggle bit
> - repeat.
>
> Without detailed proof yet, I conjecture that the reverse applies.
Got it.
Assume you have a procedure P solving the verbose statement.
To read the bit in the concise statement, apply P until the light
goes on; return 0 if it lit Green, or 1 if it lit Red.
To toggle the bit in the concise statement, apply P until the
light goes on, then off, then on.
Of course: to put the bit into some desired sate, read it, then
toggle it if it is not in the desired state.
Francois Grieu
James Dow Allen
> James Dow Allen a écrit :
Sorry, my error. I'm afraid I got a bit confused.
Specifically, I confused one bit with the bottle's bit.
> > On Feb 2, 7:08 pm, Francois Grieu <fgr...@gmail.com> wrote:
> >> We shall store a bit of information
> .
> >> - any two readings of the bit must be identical unless a change
> >> of the bit was decided in between;
> .
> Here "bit" refers to the bit to be implemented using the
> bottles.
Well it is a bit confusing, isn't it?
Using six (or more) bits to implement a single bit?
... which *is* a bit unusual.
> > I *think* I've found a 6-bottle solution for the old
> > problem, but will post it in the old thread,...
Come on, Francois! You've had practice debugging these!
Does mine work or not?
James
Francois Grieu
> Thank you. I am almost sure that I now understand the puzzle correctly.
>
> four bottles.
None of this is correct.
rec.puzzle, please try harder! This puzzle is difficult, but I find it
rewarding to construct the "bit" (unit of information used in digital
devices) from a few physical objects, with just a few real-life
constraint: we must be sure to fill a bottle only when it is fully
empty, or equivalently we can program our media only when it is erased;
and we can be interrupted at any time by e.g. power loss.
The problem again (repetition is the essence of usenet)
A bit in bottles - concise statement
We shall store a bit of information using the level of water in
a number of bottles, initially empty, under these constraints:
- any two readings of the bit (each either false or true) must be
identical unless a change of the bit was decided in between;
- we can get interrupted at *ANY* time;
- we can order to "empty" or "fill" a bottle; either can be
interrupted, which can leave the bottle neither empty nor full;
- we must not fill a bottle that is not empty;
- the information we get on bottles is only a vector of bits, one
per bottle, 0 for "not full" and 1 for "not empty"; the value
obtained for bottles neither empty nor full is arbitrary, and
in particular can change after an interruption.
Is it possible? Give a proof.
A verbose statement follows. Feasibility is equivalent, because
# to build the procedure of the verbose statement from a solution
to the concise statement, one can:
* read the bit according to solution of concise statement;
* light green or red accordingly;
* wait one second;
* turn the light off;
* toggle the bit according to solution of concise statement;
* repeat.
# to obtain a solution to the concise statement from a procedure
according to the verbose statement:
* to read the bit: apply the procedure till the light goes on,
the color gives the state of the bit;
* to set the bit to any desired state: apply the procedure
until the light goes on to the color for that state.
A bit in bottles - verbose statement
We must define a procedure which, if executed without interruption,
repeatedly: turns "on" a light either "Green" or "Red", turns it
"Off", turns it "on" again in the other color ["Red" or "Green"],
turns it "off".
Our procedure can be interrupted abruptly at *ANY* time [picture a
microprocessor which power can disappear without warning], then
restarted [most information about what was going on earlier is lost,
in particular our procedure starts again from the beginning]. Before
each (re)start, the light gets turned off automatically.
If an interruption occurs while the light is "on" in some color, then
the next time that the light is turned "on", it must be with the same
color [thus one bit of information must be kept about past history to
decide that color].
The only method to store information across interruptions is the
amount of water in 10 bottles, initially empty, that we never see.
On (re)start, our procedure is given input about each bottle, as a
vector with one element per bottle, either 0 for "not full" or 1 for
"not empty" [this gives no information for a bottle neither empty nor
full; for such a bottle, the input can vary arbitrarily from one
restart to another even if the amount of water in the bottle did not
change].
We can order to "Empty" a designated bottle [it's content is recycled
to the sea]; or to "Fill" it, which must be ordered only on an empty
bottle [this avoids overflow while this bottle's worth of water is
is pumped into it from the sea]. Each of these "Empty" or "Fill"
lasts 1 second, unless an interruption occurs, which may leave the
designated bottle neither empty nor full. Bottles are emptied and
filled one at at time. Nothing but our orders changes the amount of
water in the bottles.
Assume everything [computation, decision, actions on the light..] is
instantaneous except "Empty", "Fill", and any explicit "Wait" we may
request. In the absence of interruption, the delay from (re)start or
"Off" to "on" transition to the next such transition must not exceed
1 minute [the procedure must not stall], and each "on" state of the
light must last at least 1 second with no color change [allowing
inspection].
Does a correct procedure exist [one that never breaks any of the
"must" or asks for something of unclear feasibility or effect]?
Give a proof.
If no, try to optimize the mean time between failures under the
assumption that information given on restart about bottles neither
empty or full is assigned by coin toss, and interruptions occurs with
odds p each second; very small and very high p are especially
interesting.
If yes, try to optimize
- the number of bottles used
- the maximum time from (re)start to light on
- the flashing rate if there is not interruption
- the average flashing rate under the assumptions for "If no..".
[Best procedures may depend slightly on some additional assumptions].
I'm the author of this puzzle. It is based on a real, difficult
engineering issue [occurring in Smart Cards, which are subject to
random or adversarial power loss or reset, and store information by
injecting electrical charges into memory cells, then read it as the
charge level].
I have conclusively determined if a correct procedure exists or not.
Others on rec.puzzle have also. Revealing that bit of information
removes some of the fun of the puzzle.
Francois Grieu
Charles Bryant
Francois Grieu <fgr...@gmail.com> wrote:
}Nick Wedd wrote:
}> Thank you. I am almost sure that I now understand the puzzle correctly.
}>
}> My immediate impression was that it must be impossible.I now think
}> that there may be a solution, and if there is it must involve at least
}> four bottles.
}
}None of this is correct.
}
}rec.puzzle, please try harder!
I believe the following is a solution.
Main sequence:
State Action
ee +G -G F1
eF F0
FF +R -R e1
Fe e0
ee
Recovery performs one of these sequences:
Read Action
ee e0 e1
eF e0 F0 e1 F1
Fe e1 F1 e0 F0
FF e0 F0 e1 F1
}If yes, try to optimize
}- the number of bottles used
2
}- the maximum time from (re)start to light on
2
}- the flashing rate if there is not interruption
Every 2 (complete cycle in 4).
Daniel Giaimo
Don't you mean 4?
--
Dan G
Francois Grieu
> In article <4b6d4b9f$0$14944$426a...@news.free.fr>,
> Francois Grieu <fgr...@gmail.com> wrote:
> }Nick Wedd wrote:
> }> Thank you. I am almost sure that I now understand the puzzle correctly.
> }>
> }> My immediate impression was that it must be impossible.I now think
> }> that there may be a solution, and if there is it must involve at least
> }> four bottles.
> }
> }None of this is correct.
> }
> }rec.puzzle, please try harder!
>
> I believe the following is a solution.
>
> Main sequence:
> State Action
> ee +G -G F1
> eF F0
> FF +R -R e1
> Fe e0
> ee
>
> Recovery performs one of these sequences:
>
> Read Action
> ee e0 e1
> eF e0 F0 e1 F1
> Fe e1 F1 e0 F0
> FF e0 F0 e1 F1
I like the syntax: zero explanation is needed!
But the algorithm fails:
- a disruption occurs after +R, thus at FF
- on recovery, a disruption occurs during e1 (third op);
state is now F?
- on recovery, F? is read as FF, a disruption occurs
during e0 (first op); state is now ??
- on recovery, ?? is read as 00, +G follows, bust.
Very partial spoiler follows
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
There is no solution with 1 or 2 bottles.
Francois Grieu
Francois Grieu
Charles Bryant wrote:
> In article <4b6d4b9f$0$14944$426a...@news.free.fr>,
> Francois Grieu <fgr...@gmail.com> wrote:
> }Nick Wedd wrote:
> }> Thank you. I am almost sure that I now understand the
> }> puzzle correctly.
> }> }> My immediate impression was that it must be impossible.
> }> }> I now think that there may be a solution, and if there
> }> }> is it must involve at least four bottles.
> }
> }None of this is correct.
> }
>
> I believe the following is a solution.
>
> Main sequence:
> State Action
> ee +G -G F1
> eF F0
> FF +R -R e1
> Fe e0
> ee
>
> Recovery performs one of these sequences:
>
> Read Action
> ee e0 e1
> eF e0 F0 e1 F1
> Fe e1 F1 e0 F0
> FF e0 F0 e1 F1
I like the syntax: zero explanation is needed!
But the algorithm fails:
- a disruption occurs after +R, thus at FF
- on recovery, a disruption occurs during e1 (third op);
state is now F?
- on recovery, F? is read as FF, a disruption occurs
during e0 (first op); state is now ??
- on recovery, ?? is read as ee, +G follows, bust.
Francois Grieu
wrote in a private communication that went the wrong inbin:
> On Mon, Feb 1, 2010 at 9:44 AM, Francois Grieu <fgr...@gmail.com>
> wrote:
> <snip>
> > If you fell an itch, my best procedure is near the end of
> > http://fragrieu.free.fr/A_bit_in_bottles.txt
Wich asserts:
On restart, decide what to do according to the info about bottles:
// ABC ABC
case 000: case 001: A=0; C=0; C=1; A=1; B=0; goto lGreen;
case 010: case 011: A=0; C=0; A=1; B=0; B=1; goto lRed;
case 100: case 110: B=0; B=1; goto lRed;
case 101: case 111: B=0; goto lGreen;
// ABC ABC
lGreen: light_on_Green; A=0; light_Off; B=1; goto lRed;
lRed: light_on_Red; A=0; light_Off; B=0; goto lGreen;
> There is an error in your procedure. Suppose we start in state 000.
> Then is we follow your procedure we eventually end up in state 011
> with the red light on. Suppose we are interrupted here. When we
> come back up we attempt to go through the following state changes:
>
> 011 -> 011 -> 010 -> 110.
>
> Suppose we are interrupted halfway through the last transition above.
Bootles are ?10
> When we come back up suppose we read bottle A as not empty. Then we
> are in state 110 and we attempt to empty bottle B. Suppose we are now
> interrupted again.
Bootles are ??0
> When we come back up we read bottles A and B as empty. Then we are
> in state 000. Now the next time the light comes on it will be green,
> which violates the instructions, since it was interrupted with the
> red light on above.
Daniel Giaimo is absolutely right :-(
I feel quite ridiculous..
For the records, two persons beside me had vetted this solution correct.
I'm back to square one!!
Francois Grieu