Welcome to MindCipher, a social repository of the world's greatest brain teasers, logic puzzles and mental challenges.

Non-Adaptive 12 Identical Balls

Okay - so I posted this puzzle to reddit a few weeks ago and one guy had the following comment:

Same problem, but your solution must be non-adaptive. IOW, specify the weighings that you will make up front. You are not allowed to change them based on the results of previous weighings

So the whole problem becomes: Identify the odd (heavy or light) ball among 12 identical balls with a static plan (i.e. no conditional decisions) that uses at most 3 weighings of a balance scale.

The original puzzle is hard enough, but this variant has been killing me. I think I could come up with a solution if the original problem specified whether we expect the odd ball to be heavy or light.

Anyone have any ideas? It feels nearly impossible.

Unsolved

Comments


Jared Wells

OK here's a little thought, not sure either about a full solution: Might there be some tricky way to weigh the balls in a some overlapping sets in order to discern which ball it is exactly? I think that still causes problems when you don't know whether it's heavier or lighter though...


Jake Glascock

Label the balls A1-A6 and B1-B6.

Weigh One:

Left

  • A1
  • A2
  • A3
  • A4
  • A5
  • A6

Right

  • B1
  • B2
  • B3
  • B4
  • B5
  • B6

Weigh Two

Left

  • A1
  • A2
  • A3
  • B1
  • B2
  • B3

Right

  • A4
  • A5
  • A6
  • B4
  • B5
  • B6

Weigh Three

Left

  • A1
  • A4
  • B1
  • B4

Right

  • A2
  • A5
  • B2
  • B5

Off

  • A3
  • A6
  • B3
  • B6

Explanation: Weigh One gives you group A or B. Weigh Two gives you 1-3 or 4-6. Weigh Three gives you 1, 2, or 3 OR 4, 5, or 6.

  

Larry Fenn

heavier or lighter means your first weighing is irrelevant

  

Jake Glascock

You're right. I read the problem too quickly and failed to account for heavy or light. Solution foiled!


Josh

I just figured it out. It should be possible because each weighing has 3 outcomes so 3*3= 27 outcomes and there are only 24 different possibilities for the answer.

Let’s say you have balls ABCDEFGHIJKL

1st weighing ABCDE v FGHIJ

2nd weighing GCJE v AIDK

3rd weighing BEI v GHL

S= same, L= left side heavier, R= right side heavier for the outcomes AL = A is lighter and AH = A is heavier (for example HHH = EH)

F, K, and L are only weighed once, so if their side is heavier or lighter and the other two weighings are the same, then you know if they are heavier or lighter.

E and I and G are weighed 3 times, LLL= EH and RRR=EL and RRL= IH and LLR = IL and LRL = GH and RLR= GL

All other balls are weighed twice. If their side is heavier or lighter both times then that ball is heaver or lighter. The key to this is that none of the balls weighed twice are weighed with any of the other twice weighed balls.

All combinations except the impossible SSS, RLL, and LRR give unique answers which is also 27 possible outcomes- 3 impossible ones = 24 total outcomes

  

Satya Singamsetti

Thought provoking..

"None of the balls weighed twice are weighed with any of the other twice weighed balls". I think you meant to type this (corrected weighing) 1st weighing ABCDE v FGHIJ 2nd weighing GCJE v AIHK 3rd weighing BEI v GDL

But neither of these produce a solution.

(your weighing) If the result is LRS => Either A or D can heavy or J can be Light. So Cant say.

(Corrected weighing) If the result is LRS => Either A can heavy or J can be Light. So Cant say.

But I still like the idea. Good luck!!


Anurag Kapale

I think I have come up to a solution. Please check and try to find failing case if any (though I am pretty sure there shouldn't be any.)

spoilerdon't read this

Divide the balls in 3 sets of 4 balls each: A, B, C

*First Weighing: A1, A2, A3, A4 vs B1, B2, B3, B4

*Second Weighing: A1, A2, B1, B2 vs A3, C1, C2, C3

*Third Weighing: A1, B1, B3, C1 vs A2, B2, B4, C2

Explanation: We can consider case wise: *Case 1: all weighing are equal or First two weightings are equal: C4 as it was never taken for weightings, and all other are defect-less.

Note: We are just supposed to figure out the odd ball, it is not necessary to tell if it is heavy or light.

*Case2: First Weighting is equal; second is unequal:

Note: Without loss of generality we can assume, left was Heavy. Solution for other case would just be vice verca. as first weighting was equal: As and Bs are defect-less. left pan was heavy in second weighting so, either of C1, C2 and C3 is Light. In the third weighting we have C1 and C2 opposite to each other, whichever pan is lighter, that ball is odd and light. If the pans are equal the C3 is odd and light.

Case 3: First weighting is unequal; Again without loss of generality assume that Left was heavier. One of balls As can be heavier or one of the balls in B can be lighter. Case 3.1 in second weighting left is Heavier. That can be only because of balls A1 or A2. So, one of them is odd. In the third weighting they are in opposite pans, so whichever pan is heavier that ball is odd and heavy.

*Case 3.2: In second weighting right is heavier: That can either be because one of the balls B1 or B2 is ligher or ball A3 is heavier In the third weighting we dont have ball A3 and balls B1 and B2 are in opposite pans. So, whichever pan is ligher that ball is odd. If the pans are equal that means A3 is odd and heavier.

*Case 3.3 In second weighting pans are equal. That means none of the A1, A2, A3 or B1, B2 are defective. In the third weighting we have B3 and B4 in opposite pans, whichever pan is lighter that ball is defective. If the pans are equal, then A4 is odd and heavier.

This covers all the cases. Hope you enjoy the solution. :)


Kyle Gilbert

I think I've solved it down to a 50/50 shot. spoilernumber balls 1-12. weigh 1-4 vs 5-8. then, weigh 5-8 vs 9-12. final weighing is 3-5 vs 8-10. the first two weighings will tell you which group has the ball. if weigh 1 tilts and 2 doesn't, its 1-4. if weigh 2 tilts and 1 doesn't, its 9-12. if both tilt, its 5-8. the third weigh cuts each group in half so that if the scale tilts, you know that it is one of the two from the group already causing the scale to tilt. if it doesn't, then you know that it's one of the two that you left out from the group.

Check out other puzzles:
Random  

Like this? You might also like:
3 Coins
Don't Mate in One
Clock Works - Google Interview Question
Submitted by
Aakash
over 1 year ago
Likes
Difficulty 8.7 ?

Tags
Math logic unsolved


Back