Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Can you explain how you weigh the balls? How many do you weigh at a time and how do you decide which ones to weigh? I'm trying to follow your solution but I'm confused about this one thingn


The traditional solutions do things like: 1) split into 4 piles A,B,C. compare A,B on the balance. 2) If they balance, bad coin in 4 in pile C can easily be found. 3) If they don't balance, you know the 4 in C are good. At this point you have to fiddle by mixing coins among piles cleverly to get more weighings. But you can do it in three total. If I recall, seomthing like one from A, three from C, versus three from B, one from C, or something like that, is the next weighing.

This type of solution requires choices and branching. Mine was nicer I think since it requires no branches, and the weighings themselves spit out the bad coin number in base 3.


There's a slightly simpler solution if you don't care whether the odd ball is lighter or heavier:

It's:

X. AAAA vs BBBB

If X was balanced, XX: C1 vs C2, then XXX: C2 vs C3 (general way to distinguish 2 unknowns: weigh one unknown against one known)

If X was unbalanced, WLOG assume A was heavier. XY: A1 A2 B1 vs A3 A4 B2

Then if XY balanced, use the general method to distinguish B3 or B4 as answer.

If XY unbalanced, WLOG assume A1 or A2 is heavy, or B2 is light, so XYY A1 vs A2 finds the heavy one or implies B2 is light.


What is C1 and C2 and C3?

What is XY? What's WLOG?

Can you dumb this down a bit more please?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: