SCHOOL OF COMPUTER SCIENCE

Zeroize Me

Zeroise me

A long worm crawls into a cosmetic veterinary surgery, complaining of a problem with 1's.

A worm can be thought of as a string of 0's and 1's and the most beautiful worm is 00000 ... 0. The worm is a sequence of segments and there is a 0 or a 1 on each segment. The procedure for removing 1's is complicated. If there is a 1 at the right hand end (where the tail is), then the surgeon can remove this 1 (and the segment it lies on) and place a new segment with 0 or a 1 at the left hand end (where the head is).

If however there is a 0 at the right hand end then the surgeon can remove it, but he has no control over what appears on the new segment at the left hand end. Indeed, the surgeon has to operate under the assumption that there is an adversary making a choice of what to replace a 0 by.

The adversary would like the operation to continue indefinitely. The surgeon claims a 100% success rate. Do you believe him?

 

alanATrandomDOTmathDOTcmuDOTedu

  Previous Puzzles and Solutions

Puzzle 36 -- Nunchuk Supreme and Solution
Puzzle 35 -- Turn on the lights and Solution
Puzzle 34 -- Odd goings on and Solution
Puzzle 33 -- Abduction
and Solution
Puzzle 32 -- The Magic Money Machine
and Solution
Puzzle 31 -- Number Games and Solution
Puzzle 30 -- Darkness
and Solution
Puzzle 29 -- Seating and Solution
Puzzle 28 -- Hiking and Solution
Puzzle 27-- Another Hat Problem and Solution
Puzzle 26-- Coffee
and Solution
Puzzle 25-- Rational Creatures
and Solution
Puzzle 24 -- Fair Shares? and Solution
Puzzle 23 -- Celebrity Problem and Solution
Puzzle 22 -- Can Oleg beat Erdös? and Solution (pdf)
Puzzle 21 -- Searching for the truth
and Solution (pdf)
Puzzle 20 -- Democracy and Solution (pdf)
Puzzle 19 --  Homework Scores and Solution
Puzzle 18 -- Spiders and a Fly and Solution (pdf)
Puzzle 17 -- The Wandering Toad and Solution
Puzzle 16 -- The Hungry Lion and Solution (pdf)
Puzzle 15 -- Hat Problem and Solution (pdf)
Puzzle 14 -- Restrooms and Solution (pdf)
Puzzle 13 --The Voting Problem and solution (pdf)
Puzzle 12 -- Level with me and solution (pdf)
Puzzle 11 -- Quarelling Quartets and solution (pdf)
Puzzle 10 -- Card Tricks and solution (pdf)
Puzzle 9 --Problems with ants and solution (pdf)
Puzzle 8 -- Here comes Santa (pdf) and solution (pdf)
Puzzle 7 --The Gridville Garbash problem and solution (pdf)
Puzzle 6 --Uniform Candy Distribution and solution (pdf)
Puzzle 5 -- Empty the Bucket and Solution
Puzzle 4 ---Vacancy and solution (pdf)
Puzzle 3 ---Take the last chip and solution (pdf)
Puzzle 2 --- Lights of the Round Table and Solution (pdf)
Puzzle 1 --- Managers and Engineers and Solution