Congratulations to all the winners:
Ula U
Pedro Miguel
vera73
Thank you all for your participation, You are smarter than 6th grader or maybe on the same level :-)... just kidding.
You all got it right! Some of you were impatient to get the correct answer so I'm doing this post a bit earlier than I should.
All of you that are interested in the answer to the problem that I posted yesterday, click on the following link and read comments.
http://spforsquirrels.blogspot.com/2008/11/are-you-smarter-than-6th-grader.html
Enjoy
3 comments:
Heh, I'm glad I ran into a sharepoint problem, and Google told me your blog might be able to help :)
The riddle was a nice break from work.
The link to the solution is no longer up so I can't see which of the many solutions you made the answer, but I've always loved that problem and can't resist chiming in. Being able to work out an answer is a great feat for a 6th grader.
It's also interesting to solve the general problem of "Is it possible to determine one lighter or heavier ball out of x balls with y weighings"
The interesting to note that 4 balls with 2 weighings is impossible. Even though 2 weighings with 3 possible outcomes (left, right or even) leaves room to code for 9 possibilities and you should only need 8 (4 balls, each heavy or light).
With three weighings, you can solve it for up to 12 balls. One example of many possible solutions:
R=Right side heavy
L=Left side heavy
E= Even
Ball light heavy
1 RRR LLL
2 RLL LRR
3 LEE REE
4 LER REL
5 ELL ERR
6 LLE RRE
7 RRE LLE
8 RRL LLR
9 LEL RER
10 ERE ELE
11 EER EEL
12 ELR ERL
You can work back to a solution from the balls on a scale perspective from this key, just leave the ball off the scale if the required result is even. There are many solutions, but I don't think I could intuit a solution for 12 balls in 3 weighings the same way you can for 8 balls.
Thirteen balls with three weighings is impossible for the same reason 4 is with 2 weighings (or I would guess 40 balls with 4 weighing but I'm not going to try to prove that): Each weighing needs to have the same number of right and left possible outcomes in the answer key since that means there that weighing will have the same number of balls on each side of the scale. Since an all even result can't be used, one of the other sets of weighing results also can't be used.
Thanks Natalya, it's a neat problem to think about for information technology people, it involves permutational complexity and importance of context: not every mathmatically feasible solution is possible because the context of the scale links each weighing result set with it's mirror image and mandates both sides of the scale must always have the same number of balls.
Oops, there's a typo on the 12 ball solution example. In my first comment.
This example is better:
Ball light heavy
1 RRR LLL
2 RLL LRR
3 RRE LLE
4 RER LEL
5 LEE REE
6 LRL RLR
7 LRE RLE
8 LER REL
9 ELE ERE
10 EEL EER
11 ELR ERL
12 ELL ERR
Post a Comment