Re: LOGO-L> False coin problem

["Olga Tuzova" <olgatu@ort.spb.ru>]

Pierre-Andre,

Thank you very much for the solution you've sent me. I like it very 
much. Though my students are not ready yet to follow it, I think, 
this solution just shows the style of programming where I should 
direct them.

Thank you,
Olga.

> To:            "Olga Tuzova" <olgatu@ort.spb.ru>
> Date:          Mon, 09 Feb 1998 11:50:17 -0700
> From:          "Dreyfuss Pierre-Andre" <p.a.dreyfuss@mailexcite.com>
> Cc:            logo-l@gsn.org
> Subject:       Re: LOGO-L> False coin problem
> Organization:  MailExcite  (http://www.mailexcite.com)

> Here is a way to use logo for this problem with pupils.
> 
> First create a microworld to let them search an algorithm.
> 
> coins make a stack of coins with a false coin choosed randomly, it uses falsecoin.
> 
> 
> to  coins
> falsecoin 1 + random 12  ifelse 0 = random 2 [.1][-.1]
>    
> end
> 
> to falsecoin :n :extra
> repeat 12[make word "c repcount ifelse :n = repcount ~
>      [1 +:extra][1]]
> end
> 
> The coins are named c1 c2  c3 ...
> 
> They are variables containing  1 or (1.1 or .9) for the false one.
> 
> You have to put on the plates of the scale a list of coin.
> 
> 
> The procedure oldscale let test the weights, 
> 
> It output the character < , =, or >.
> 
> to oldscale :x :y 
> localmake "s1 reduce "sum map [thing ? ] :x
> localmake "s2 reduce "sum map [thing ? ] :y
> if :s1 = :s2 [op "=]
> op ifelse :s1 > :s2  [">]["<]
> end
> 
> 
> You can build and test the algorithm with commands such that one :
> 
> show oldscale [c1 c2 c3 c4][c5 c6 c7n c8]
> 
> 
> Here is a solution :
> 
> to solve
> localmake "l1 [c1 c2 c3 c4 ]
> localmake "l2 [c5 c6 c7 c8 ]
> localmake "l3 [c9 c10 c11 c12]
> test  "= = oldscale :l1 :l2 
> iftrue [solve2 :l1 :l3 :l2 ]; the false one in  l3.
> iffalse[solve2 :l3 :l1 :l2 ]; either in l1 or in l2
> end
> 
> to solve2 :r1  :r2 :r3 
> localmake "res oldscale  :r2 :r1
> 
> if "= = :res[solve2 :r1 :r3 :r2 stop]; the false one is in r3
> 
> solve3 (list item 1 :r2 ) (list item 2 :r2 ) (list  item 3 :r2)~
>        (list item 4 :r2 ) :res 
> end
> 
> to solve3 :r1 :r2 :r3 :r4 :res 
> localmake "res2 oldscale :r1 :r2 
> 
> if "= = :res2 [solve3 :r3  :r4 :r1 :r2 :res  stop ]
> ifelse  :res2 = :res [ pr se :r1 thing first :r1 ][pr se :r2 thing first :r2] 
> end
> 
> You can test your algorithm with.
> 
> repeat 12 [falsecoin  repcount .1 pr repcount solve]
>  and
> repeat 12 [falsecoin  repcount -.1 pr repcount solve]
> 
> and cheat with:
> 
> show filter [not 1 = thing ?] [c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12]
> 
> Regards.
> 
> P-A Dreyfuss
> 
> 
> 
> 
> 
> Olga wrote.
> 
> >Here is a false coin problem.
> >
> >Somehow I've missed it when it has been posted, but as far as I know, 
> >it hasn't been discussed yet. Sorry, if it isn't so.
> >
> >Chuck  formulated it in the therms of balls, but as in my 
> >childhood I was introduced to it as a problem of false coin, I'll 
> >reproduced it in the coins therms.
> >
> >You have 12 coins, all look alike, 
> >but one of them is false and  of a different weight (either lighter 
> >or heavier, you don't know). You have an old fashioned scale that 
> >allows only comparisons (equal, less than, greater than).  Can you 
> >determine using at most three measurements which coin is false?
> >
> >We were discussing this problem with the 6th graders on our faculty 
> >lesson and they were quite good in solving it. Though, our goal was 
> >to work out just a verbal algorithm. Frankly, I couldn't write more 
> >or less elegant program myself and would be grateful for any ideas 
> >and proposals. The  direct translation of the  algorithm below looks 
> >extremely clumsy. Nevertheless I'm sure just the discussion of the 
> >problem and developing the verbal algorithm could be very useful.
> >
> >-----------------------------------------
> >So, let's determine which coin is false.
> >
> >First, let's give each coin a number from #1 through #12.
> >
> >Step 1.
> >Let's put the coins #1, #2, #3, #4 on the left side of the scale and 
> >coins #5, #6, #7, #8 - on the right side.
> >If there is an equilibrium, then the false coin is among #9, #10, 
> >#11, #12 and we should go the Step 2, otherwise - to the Step 4.
> >
> >Step 2.
> >Let's put "pure" coins #1, #2, #3 onto the left side of the scale and 
> >#9, #10, #11 - onto the right side.
> >If there is an equilibrium, then the false coin is #12 and the 
> >problem is solved!
> >Otherwise we should go to the Step 3.
> >
> >Step 3.
> >Now we know that the false coin is among #9, #10, #11 and we also got 
> >to know whether it's lighter or heavier than the "pure" one.
> >It's not difficult now to determine the false coin among three shady 
> >ones, isn't it? And the problem is  solved!
> >
> >Step 4.
> >Now the situation is more complicated. We have eight shady coins and 
> >we know nothing about it's being lighter or heavier than the pure 
> >ones.
> >This step is the most tricky.
> >Let's call the coins which were on the "heavier" side "heavy" coins 
> >and those which were on the "lighter" side - "light" ones.
> > Let's consider that the left side of the scale was more heavy. In 
> >the opposite case the solution will be the same.
> >So, coins #1, #2, #3, #4 are " heavy"  and  coins #5, #6, #7, #8 are 
> >"light", that is, if the false coin is in the first group, it's 
> >heavy, otherwise it's light..
> >
> >Let's put "heavy"  coins #1, #2, #3 and one "light" coin #8 on the 
> >left side. On the right side let's put three "pure" coins #9, #10, 
> >#11 and one "heavy" coin #4.
> >
> >If the left side is lighter than the right one, the false coin is 
> >among #8  an #4. It's not so difficult to determine it with one  
> >measurement, isn't it? The problem is solved!
> >
> >If the left side is more heavy, then the false coin is among    #1, 
> >#2, #3 and we got to know, it's heavier than the "pure" one. Now, 
> >with just one measurement we can determine it, can't we? The problem 
> >is solved!
> >
> >If there is an   equilibrium, then the false coin is among "heavy" 
> >coins #5, #6, and #7 and we know, it's more heavy. In this case we 
> >can solve the problem with the one  measurement!
> >-------------
> >Congratulations! No more cases are left. 
> >
> >If my long story, which looks like a novel (a detective?), fails to 
> >be understandable, I hope there are volunteers to make it more clear, 
> >if the problem is in English,  in other cases I'd be glad to answer 
> >any questions and to describe some places more detailed wherever it's 
> >needed. I'm sure, the problem deserves attention and it's very 
> >useful in teaching to develop algorithms.
> >
> >Regards,
> >Olga.
> >---------------------------------------------------------------
> >Please post messages to the Logo forum to logo-l@gsn.org.  Mail
> >questions about the list administration to logofdn@gsn.org.  To
> >unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.
> >
> 
> 
> 
> Free web-based email, Forever, From anywhere!
> http://www.mailexcite.com
> 
---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.