Extremely Difficult Logic Problem

Welcome to Hypography, a forum for science and technology. Registration is fast, simple and absolutely free so please, join our community today! If you have any problems with the registration process or your account login, please contact us.

		Science Forums > Help and Advice > Questions and Answers
Extremely Difficult Logic Problem

Page 1 of 2

LinkBack

Question Tools

Published by User2983 10-15-2007

You have 12 pencils. 11 of them are exactly the same weight and the other one is either HEAVIER or LIGHTER. Determine which one is the odd pencil by using a balance beam only 3 times. HINT: for the first balance, use four on each side.

I cannot figure this one out to save my life and I've been working on it for a while.

By Inter.spem.et.metum on 10-15-2007

Re: Extremely Difficult Logic Problem

If you don't an equal weight on both sides with the first eight pencils it won't work. If you do, then you have four pencils left with one being the pencil you are looking for. Then label the four pencils according to the side you put it on. For example, A1 and A2, and B1 and B2. Weigh the four and remember which side weighs less. Take off A1 and B1. If one of the sides still weigh less, then you have your answer. If not, whichever side weighed less than the other before you removed first two pencils was the side that held the lighter pencil.

By User2983 on 10-15-2007

Re: Extremely Difficult Logic Problem

Quote:

Originally Posted by Inter.spem.et.metum

but you don't know if the pencil is lighter or heavier

By Erasmus00 on 10-15-2007

Re: Extremely Difficult Logic Problem

First, measure 4 and 4. If they weigh the same, you have narrowed the special pencil down to 4, which also gives you 8 control pencils.

Now, measure 2 of the remaining 4 against two control pencils. After this weighing, you have narrowed the special pencil down to one of two. Measure on of these remaining pencils against one of the control pencils. This will allow you to determine the special pencil.

Now, if the original 4 did not weigh the same, then you again have control pencils, but you have 8 uncertain pencils. However, we have extra info- 4 of these pencils weighed "heavy" and 4 weighed "light."

Take 3 heavy pencils and 3 light pencils and weigh them against controls. If its heavier, you know that a. the special pencil is heavier, and b. one of your three heavy pencils is the special one. Hence, the third weighing is one of the heavy pencils against one of the other heavy pencils. If they are teh same, the odd man out is special, else the heavier pencil is special. Same thing if it weighed lighter then the controls.

The last case is you get the same thing when you do this second weighing. So now we have 1 heavy pencil and 1 light pencil. Take either one and weigh it against a control.
-Will

Last edited by Erasmus00; 10-15-2007 at 03:31 PM.

By Inter.spem.et.metum on 10-15-2007

Re: Extremely Difficult Logic Problem

Yes you would.

Side A (A1...A2) (B2....B1) B Side
Weight 1.00 Weight 0.99

Take off A1 and B1.

IF:

Side A (A2) (B2) B Side
Weight .50 Weight .50

Then B1 is the lighter pencil.

IF:

Side A (A2) (B2) B Side
Weight .50 Weight .49

Then your answer is obvious. How would this not work?

By User2983 on 10-15-2007

Re: Extremely Difficult Logic Problem

Quote:

Originally Posted by Inter.spem.et.metum

No, you're right. That would work. I just read it wrong.

By LaurieAG on 10-16-2007

Re: Extremely Difficult Logic Problem

Quote:

Originally Posted by User2983

Hi User2983,

This puzzle is a variant of the old 9 gold coins with one 'dud', determined from 2 weighings of a beam balance (note the dud is lighter than gold).

1. Separate into groups of 3 and compare 2 on the beam balance. If one of these 2 groups goes higher than the other select it, otherwise select the third untested set.

2. of the selected set compare two of the coins on the balance. If they both balance the third untested coin is the dud, otherwise the coin that goes higher is the dud.

By CraigD on 10-17-2007

A tested solution, and a more difficult problem

Everything seemed OK with Erasmus’s approach until the second weighing when the first 4 and 4 weighing wasn’t the same

Quote:

Originally Posted by Erasmus00

… Take 3 heavy pencils and 3 light pencils and weigh them against controls.

This would work if I had 6 control pencils, but I only have the 4 not used in the first weighing.

I found (at Analytical Puzzles - Very Difficult – the internet has made a talentless, cheating hack of me

) this algorithm, and tested it. Writing it in ordinary English seemed clumsy, so I used a simple code:

“0: (1,2,3,4)-(5,6,7,8)” means “to begin, weigh pencils # 1,2,3 and 4 against 5,6,7 and 8”.
“0,-1: (1,2,5)-(3,6,9)” means “if the right side is heavier, weigh 1,2,3 against 3,6,9”.
Each step has the label of the previous step, followed by -1 if the right side is heavier, 0 if they balance, and 1 if the left side is heavier.
A line with a single number following the “:” means “the answer is “ the number.

Code:

 0: (1,2,3,4)-(5,6,7,8)
 0,-1: (1,2,5)-(3,6,9)
  0,-1,-1: (1)-(2)
   0,-1,-1,-1: 1
   0,-1,-1,0: 6
   0,-1,-1,1: 2
  0,-1,0: (7)-(8)
   0,-1,0,-1: 8
   0,-1,0,0: 4
   0,-1,0,1: 7
  0,-1,1: (3)-(9)
   0,-1,1,-1: 3
   0,-1,1,0: 5
 0,0: (9,10)-(8,11)
  0,0,-1: (9)-(10)
   0,0,-1,-1: 9
   0,0,-1,0: 11
   0,0,-1,1: 10
  0,0,0: 12
  0,0,1: (9)-(10)
   0,0,1,-1: 10
   0,0,1,0: 11
   0,0,1,1: 9
 0,1: (5,6,1)-(7,2,9)
  0,1,-1: (5)-(6)
   0,1,-1,-1: 5
   0,1,-1,0: 2
   0,1,-1,1: 6
  0,1,0: (3)-(4)
   0,1,0,-1: 4
   0,1,0,0: 8
   0,1,0,1: 3
  0,1,1: (7)-(9)
   0,1,1,-1: 7
   0,1,1,0: 1

For example, if the odd pencil is #6, and it’s heavier, the following would be executed:

Code:

 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =-1
   0,-1,-1: (1)-(2) =0
    0,-1,-1,0: 6

Here’s the bit of MUMPS code I wrote to read in the algorithm code and apply it to a collection of pencils represented by A(1) … A(12):

Code:

r X2,X3 ;a couple of useful bits of code xecuted by the main program
n (A,R) s B=R,R=0 f I=1:1:(B,"+") s R=R+A((B,"+",I)) ;adds a string of pencils
f I=1:1:12 s A(I)=5 ;set all 12 pencils equal
k D f  r R,! q:R=""  s R=(R," "),@("D("_(R,":")_")=(R,"":"",2)") ;read the algorithm into something easy to reference
;paste the algorithm code here, followed by a blank line
f A1=6,4 f I1=1:1:12 x X3 s A(I1)=A1 w ! s N=(D(0)) f   s V=@N w ?(N),(N,3,(N)-1),": ",V q:V  s V=(V,",()","+"),R=(V,"-") x X2 s T=R,R=(V,"-",2) x X2 s T=T-R,N=(@N@(T>0-(T<0))) w " =",T,! ;the main program – shows the algorithm executing for a heavy or light pencil in each of the 12 positions

Here’s its output:

Code:

 0: (1,2,3,4)-(5,6,7,8) =1
  0,1: (5,6,1)-(7,2,9) =1
   0,1,1: (7)-(9) =0
    0,1,1,0: 1
 0: (1,2,3,4)-(5,6,7,8) =1
  0,1: (5,6,1)-(7,2,9) =-1
   0,1,-1: (5)-(6) =0
    0,1,-1,0: 2
 0: (1,2,3,4)-(5,6,7,8) =1
  0,1: (5,6,1)-(7,2,9) =0
   0,1,0: (3)-(4) =1
    0,1,0,1: 3
 0: (1,2,3,4)-(5,6,7,8) =1
  0,1: (5,6,1)-(7,2,9) =0
   0,1,0: (3)-(4) =-1
    0,1,0,-1: 4
 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =1
   0,-1,1: (3)-(9) =0
    0,-1,1,0: 5
 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =-1
   0,-1,-1: (1)-(2) =0
    0,-1,-1,0: 6
 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =0
   0,-1,0: (7)-(8) =1
    0,-1,0,1: 7
 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =0
   0,-1,0: (7)-(8) =-1
    0,-1,0,-1: 8
 0: (1,2,3,4)-(5,6,7,8) =0
  0,0: (9,10)-(8,11) =1
   0,0,1: (9)-(10) =1
    0,0,1,1: 9
 0: (1,2,3,4)-(5,6,7,8) =0
  0,0: (9,10)-(8,11) =1
   0,0,1: (9)-(10) =-1
    0,0,1,-1: 10
 0: (1,2,3,4)-(5,6,7,8) =0
  0,0: (9,10)-(8,11) =-1
   0,0,-1: (9)-(10) =0
    0,0,-1,0: 11
 0: (1,2,3,4)-(5,6,7,8) =0
  0,0: (9,10)-(8,11) =0
   0,0,0: 12
 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =-1
   0,-1,-1: (1)-(2) =-1
    0,-1,-1,-1: 1
 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =-1
   0,-1,-1: (1)-(2) =1
    0,-1,-1,1: 2
 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =1
   0,-1,1: (3)-(9) =-1
    0,-1,1,-1: 3
 0: (1,2,3,4)-(5,6,7,8) =-1
  0,-1: (1,2,5)-(3,6,9) =0
   0,-1,0: (7)-(8) =0
    0,-1,0,0: 4
 0: (1,2,3,4)-(5,6,7,8) =1
  0,1: (5,6,1)-(7,2,9) =-1
   0,1,-1: (5)-(6) =-1
    0,1,-1,-1: 5
 0: (1,2,3,4)-(5,6,7,8) =1
  0,1: (5,6,1)-(7,2,9) =-1
   0,1,-1: (5)-(6) =1
    0,1,-1,1: 6
 0: (1,2,3,4)-(5,6,7,8) =1
  0,1: (5,6,1)-(7,2,9) =1
   0,1,1: (7)-(9) =-1
    0,1,1,-1: 7
 0: (1,2,3,4)-(5,6,7,8) =1
  0,1: (5,6,1)-(7,2,9) =0
   0,1,0: (3)-(4) =0
    0,1,0,0: 8
 0: (1,2,3,4)-(5,6,7,8) =0
  0,0: (9,10)-(8,11) =-1
   0,0,-1: (9)-(10) =-1
    0,0,-1,-1: 9
 0: (1,2,3,4)-(5,6,7,8) =0
  0,0: (9,10)-(8,11) =-1
   0,0,-1: (9)-(10) =1
    0,0,-1,1: 10
 0: (1,2,3,4)-(5,6,7,8) =0
  0,0: (9,10)-(8,11) =1
   0,0,1: (9)-(10) =0
    0,0,1,0: 11
 0: (1,2,3,4)-(5,6,7,8) =0
  0,0: (9,10)-(8,11) =0
   0,0,0: 12

Notice that, with this algorithm, if the odd pencil is in position 12, it takes only 2 weighings to find it. For all other positions, it takes 3.

Clever and hard as this problem is, I don’t think it can be left alone until a general algorithm for generating the algorithm for a collection of any number of pencils is written. Anyone in? I am.

By TheBigDog on 10-18-2007

Re: Extremely Difficult Logic Problem

I can use 15 pencils and find the answer in 3 weighs.

#1) 1234 vs 5678

If one side is lighter you divide it in half and proceed, otherwise you take the next four and proceed.

#2) 12 vs 34 -or- 56 vs 78 -or- 9A vs BC

If one side is lighter you divide it in half and proceed, otherwise you take the next two and proceed.

#3) 1 vs 2 -or- 3 vs 4 -or- .... D vs E

If one side is lighter that is the answer, otherwise the unweighed pencil is the answer.

It will always take 3 tries to find the answer.

Bill

By CraigD on 10-18-2007

No knowing if the odd pencil is light or heavy / a knowledge management problem

Quote:

Originally Posted by TheBigDog

But will it work if you only know that one pencil has a different weight, not whether its lighter or heavier? In the original 12-pencil puzzle, you don’t have this datum.

Quote:

Originally Posted by User2983

You have 12 pencils. 11 of them are exactly the same weight and the other one is either HEAVIER or LIGHTER.

Another interesting variation is to require that you must always weight all of the pencils (only works for even numbers of pencils, of course). For example, if the odd pencil is #9, you could find this in 5 tries as follows:
1+2+3+4+5+6-7-8-9-10-11-12 = -1
1+2+3+7+8+9-4-5-6-10-11-12 = 1
1+2+3+4+5+7-6-8-9-10-11-12 = -1
1+2+3+4+6+8-5-7-9-10-11-12 = -1
1+2+3+4+5+9-6-7-8-10-11-12 = 1

I’ve played with the general problem a bit. I’ve not started looking at the “generate an algorithm” problem yet, but have concluded that this is a knowledge-managing problem (More commonly known to the paper-and-pencil puzzle book consumer as a “logic problem”). For example, if we write what we know about the pencils as a list with “+” and “-“ in each position if we don’t know that that pencil is not either heavier or lighter than the others, finding a heavy #9 pencil looks like this:
+-,+-,+-,+-,+-,+-,+-,+-,+-,+-,+-,+-
1+2+3+4-5-6-7-8=0 : ,,,,,,,,+-,+-,+-,+-
9+10-8-11=1 : ,,,,,,,,+,+,-,
9-10=1 : ,,,,,,,,+,,,

Page 1 of 2

Bookmarks

Currently Active Users Viewing This Question: 1 (0 members and 1 guests)

Question Tools
Show Printable Version Email this Page

Posting Rules
You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Trackbacks are On Pingbacks are On Refbacks are On

Similar Threads
Question	Question Starter	Category	Comments	Last Post
How difficult is quitting smoking?	robnibg	Psychology	6	10-10-2007 07:30 PM
A Simple, Yet Difficult, Math Problem	Sebastian	Science Projects and Homework	27	06-01-2007 04:22 AM
Confusion and Logic	ShadowMind	Philosophy and Humanities	85	04-26-2006 07:45 AM
-help?-bit on the wrist by an extremely pissed off cat	Loricybin	Medical Science	18	04-12-2006 09:16 PM
Is the English language difficult to learn ?	C1ay	Watercooler	28	09-06-2005 05:35 AM

All times are GMT -8. The time now is 01:25 AM.

Extremely Difficult Logic Problem

Hypography?

Share the love!

Sponsors

Friends