# Six spheres, six weighings.

If you grow impatient with the narrative, you can skip to the TL;DR, below.

An engineer was walking across the street, on the way back from lunch, when bam, hit by a bus.

She opened her eyes, to see a man standing before her, with pointy teeth, bloodshot eyes, and spiral horns. The man held a 3-pronged spear in his left hand and 6 shiny spheres in his right. He twitched his fingers and the spheres danced around one another, like David Bowie, but with more fingers.

"What am I doing here?"

"Well, you died..."

"I figured that much out, but what am I doing here?"

"Well, you led a mostly virtuous life, but you did have a habit of eating tunafish on Tuesdays..."

"Eating tuna on Tuesdays is forbidden? No one ever told me that!"

"They didn't? How unfortunate for you." He grinned. "Anyway, as I said, you led a mostly virtuous life, so you are being granted the opportunity to fight for your eternal soul. Metaphorically, of course. I have a puzzle for you. Solve it, and you can take the stairway up. Fail, and go the other direction."

Having worked many years as an engineer, she was used to ridiculous demands. "OK, what's the puzzle?"

"Notice that these spheres are different colors. Note that they also have different weights. Each one has a unique weight of either 1001, 1002, 1003, 1004, 1005, or 1006 grams. Over there by that door are six holes. To open the door, put the spheres in the holes in order, lightest to heaviest, from left to right. Then you may leave. Put them in in any other order, and the trapdoor below you opens. You can guess where that leads."

"How am I supposed to differentiate such minute weight differences?"

"With this." The man planted the base of the spear into the dirt. The three points morphed and dropped, turning into three pans. "This is a three-pan balance. Put things into the pans, set the whole thing spinning, and when it stops spinning, the lightest pan will rise."

He handed her the six spheres. "You will not be able to mark or alter the spheres in any way, but as you see, they are six different colors, and I assure you the colors won't change. You may scratch notes in the dirt, if you like."

She hefted the spheres. Sure enough, they all felt the same. She estimated they were about 10cm in diameter.

He raised a finger. "Oh, and I almost forgot to mention: you are only allowed a maximum of six weighings. Experiment all you like, but once you start the scale spinning, you are committed. After the sixth weighing, the scale will revert back to a spear. Also, don't bother trying to guess. The spheres were arranged by my pet precognitive demon who divined exactly what steps you would take. If you get to a point where the the answer is ambiguous, whatever guess you make will be wrong."

She experimented putting spheres into the pans. The pans were cups, shaped to match the bottom 1/3 of the spheres.

When she tried balancing two spheres onto one pan, she couldn't get it to work. "Can I really only put one sphere per pan?"

"Correct. If you attempt to put two or more spheres on a pan, you will not succeed."

"Hmm. What happens if there is no lightest pan? What if the two lightest pans held the same weight?"

"The spheres are all different weights, so you can't really do that. But if you somehow managed to, then no pan would rise."

She did some thinking, scribbled in the dirt. "Am I under any time pressure?"

"No, you literally have forever. Take as long as you like."

She did two weighings and noted the results. While she was contemplating what to do next, she heard a snip and felt something bounce off the back of her head. She caught it as she turned around. The man was sitting on a barrel, using a pair of shears to trim his toenails.

"Seriously?"

He looked up. "You looked like you might be a while. And these things do grow deucedly fast, so I figured, while I wait..." snip ... catch

"You realize the puzzle you've given me is impossible, right?"

"Oh really? Surely you know that $6! < 3^6$, so it ought to be possible. Or are you just giving up already?"

"That's not what I said..." snip ... catch

She looked down at the clippings she had caught. They were each about 1cm across. "Say, these are all remarkably similar."

"Yeah, like I said, they grow fast. After snipping each one literally millions of times, I've grown rather consistent. Each of my toenail clippings weighs exactly one gram."

"Exactly?"

snip ... catch "Yep."

"That's great." She turned around and did a bunch more scribbling in the dirt. "Ah ha!" She then did the rest of her weighings, took the spheres over to the door, put them in the holes, and with heavenly chimes, the door opened. Behind it was a staircase leading up.

"Well, that's a first," the man said.

She peered up the staircase. The top was lost in the distance. "How far is it?"

"How far do you think, from the center of the Earth to the top of the sky? Only about a hundred...million steps. Have a nice climb!"

And the door slammed behind her, echoes of his cackling lingering on the air.

TL;DR

You have six spheres, identical except for color and weight. The weights are 1001, 1002, 1003, 1004, 1005, and 1006 grams. By hand, you cannot possibly distinguish them.

You have a three-pan balance. Put whatever you like in the pans, activate the scale, and if there is a unique lightest pan, that pan will rise. If there is no unique lightest pan, no pan will rise. This scale differs from those in other puzzles in that you cannot put 2 or more spheres onto any one pan at a time.

You have six weighings to sort the spheres from lowest weight to highest.

You also have up to 10 toenail clippings, which each weigh exactly one gram. These are not provided until after you've made your first two weighings.

Your plan needs to solve all possible combinations, with no ambiguity, and zero chance of needing to guess.

How did she do it?

Bonus question: What is the minimum number of clippings needed?

• So, is it assumed that we know we'll get the clippings later? – Malady Jun 16 '15 at 0:11
• Can we reuse the clippings? So if I use 3 clippings, do I have 7 left to use, or I still have 10 to use next time? – Eli Jun 16 '15 at 6:15

This is a rather inelegant answer, produced by trying combinations until one splits the remaining search space into roughly equal parts. It requires all ten clippings, if they aren't reusable.

First, weigh three random spheres together. Call the one that rises A and the others B and C.

Weigh the other three spheres together. Call the one that rises D and the others E and F.

Each of these operations divides the total possibilities by 3, so there are 80 left to distinguish.

Now weigh B and C against D with three clippings. Call this weighing 3.

If B rises in weighing 3, there are 24 possibilities left. Weigh B with two clippings against E and F. (4a)

If B rises again in 4a, it is the 1002-gram sphere and A is 1001 grams. Weigh C, D, and E. Whichever of C and D rises is 1003, and the other one is 1004. Then weigh the 1004-gram sphere and two clippings with E and F; whichever rises is 1005 and the other is 1006.

If E rises in 4a, weigh B, D with two clippings, and E. (5a)

If B rises in 5a, it is 1003 grams, A is 1001 grams, D is 1002 grams, and E is 1004 grams. Weigh E with two clippings against C and F; whichever rises is 1005.

If E rises in 5a, it is 1003, B is 1004, D is 1002, and A is 1001. Weigh B with two clippings against C and F.

If no pan rises in 5a, D is 1001, B is 1003, E is 1004, and A is 1002. Weigh E against C and F.

If F rises in 4a, do the same thing but with E and F switched.

If no pan rises in 4a, weigh D and three clippings against E and F. (5b)

If D rises in 5b, it is 1001, A is 1002, B is 1003, and C is 1004. Weigh C and two clippings against E and F to determine which is 1005.

If E rises in 5b, it is 1004, A is 1001, B is 1002, and D is 1003. Weigh E and two clippings against C and F.

If F rises in 5b, do the same thing with E and F switched.

If no pan rises in 5b, D is 1002, A is 1001, B is 1003, and C is 1004. Weigh C and two clippings against E and F.

This identifies all possibilities where B rises in 3. If C rises in 3, the same is done with B and C reversed.

If D rises in 3, it is 1001, and B and C are 1005 and 1006 in either order, leaving 12 cases. Weigh A, E, and F; whichever rises is 1002. Then weigh the other two against B; whichever rises is 1003 and the other is 1004. Finally, weigh B and C against the 1004-gram sphere with two clippings to identify 1005 and 1006.

In the remaining 20 cases, no pan rises in weighing 3. Weigh A with one clipping against E and F. (4b)

If A rises in 4b, it is 1001 and D is 1002. E and F are 1003 and 1004 in either order. Weigh both against B to determine which is which, then weigh B and C against 1004 and two clippings to identify 1005 and 1006.

If E rises in 4b, it is 1002, A is 1003, and D is 1001. Weigh B, C, and F to find 1004, and use the last weighing to find 1005 and 1006.

If F rises in 4b, do the same with E and F reversed.

If no pan rises in 4b, A is 1002 and D is 1001. Weigh B with a clipping, C, and E with a clipping. (5c)

If B rises in 5c, it is 1004, C is 1006, E is 1005, and F is 1003.

If C rises in 5c, it is 1004 and F is 1003. Use the last weighing to find 1005 and 1006.

If E rises in 5c, it is 1003 and B is 1004. Use the last weighing to find 1005 and 1006.

If no pan rises in 5c, there are three cases left. Distinguish them by weighing B, C with a clipping, and F with two clippings. (6)

If B rises in 6, it is 1004, C is 1005, F is 1003, and E is 1006.

If C rises in 6, it is 1004, B is 1006, F is 1005, and E is 1003.

If no pan rises in 6, B is 1005, C is 1004, F is 1006, and E is 1003.

• Nicely done. Clear descriptions of the weighings and interpretations of the results. My solution only required two clippings, but that's a quibble. – user3294068 Jun 17 '15 at 19:39

It is possible with at most 2 clippings per weighing.

No solution is possible with at most 1 clipping, because there is no weighing which can tell apart the two heaviest balls, even if it was known which two balls were the two heaviest. (Thanks to f'' for providing the proof.)

My solution with two clippings

In my solution, I label the balls by using a map from colors to letters. Initially, name the balls A to F in arbitrary order, i.e. write down an arbitrary mapping from color to letter. When ordered to do so in the solution, change letters in that map, and work with the new labels in the following. This is done to reuse the same sub-solution for multiple intermediate weighing outcomes. A final result will give the letters in increasing order of weight, and you use the current map from color to letter to find the weigh of each color.

The first two weighings are the same as in the solution of user13217, namely:

W1. Weigh A vs B vs C. (720 permutations left.)

• If B is lightest, swap A<->B.
• If C is lightest, swap A<->C.

W2. Weigh D vs E vs F. (240 permutations left.)

• If E is lightest, swap D<->E.
• If F is lightest, swap D<->F.

From here on, we may use clippings.

W3. Weigh A+2 vs B vs C. ("A+2" means ball A and 2 clippings on one pan.) (80 permutations left.)

• If A+2 is lightest, swap B<->D and C<->E, and go to W4.1.
• If B is lightest, go to W4.2.
• If C is lightest, swap B<->C and go to W4.2.
• If no pan is lightest, cyclically relabel B->D->C->B, and go to W4.3.

W4.1. Weigh B+2 vs C vs F. (16 permutations left.)

• If C is lightest, goto W5.1.
• If F is lightest, cyclically relabel C->F->E->D->C, and go to W5.1.
• If no pan is lightest, swap A<->B, cyclically relabel D->F->E->F, and go to W5.2.

W4.2. Weigh B+2 vs E vs F. (20 permutations left.)

• If B+2 is lightest, go to W5.2.
• If E is lightest, cyclically relabel A->D->E->C->B->A, and go to W5.3.
• If F is lightest, cyclically relabel A->D->F->E->C->B->A, and go to W5.3.
• If no pan is lightest, cyclically relabel C->D->E->C, and go to W5.4.

W4.3. Weigh C vs D vs E. (24 permutations left.)

• If C is lightest, go to W5.5.
• If D is lightest, swap C<->D, and go to W5.5.
• If E is lightest, swap A<->B, cyclically relabel C->E->D->C, and go to W5.6.

W5.1. Weigh D vs E vs F. (6 permutations left.)

• If D is lightest, go to W6.
• If E is lightest, swap D<->E, and go to W6.
• If F is lightest, cyclically relabel D->F->E->D, and go to W6.

W5.2. Weigh C vs D vs E. (4 permutations left.)

• If C is lightest, go to W6.
• If D is lightest, swap C<->D, and go to W6.

W5.3. Weigh B vs C vs D+1. (5 permutations left.)

• If B is lightest, go to W6.
• If D+1 is lightest, the weight order is A,D,F,B,C,E.
• If no pan is lightest, cyclically relabel B->D->C->B, and go to W6.

W5.4. Weigh D vs E vs F. (6 permutations left.)

• If D is lightest, go to W6.
• If E is lightest, cyclically relabel A->C->B->A, swap D<->E, and go to W6.
• If F is lightest, cyclically relabel D->F->E->D, and go to W6.

W5.5. Weigh D vs E vs F+1. (8 permutations left.)

• If D is lightest, go to W6.
• If E is lightest, swap D<->E and go to W6.
• If F+1 is lightest, swap A<->B, cyclically relabel C->F->E->D->C, and go to W6.
• If no pan is lightest, cyclically relabel D->F->E->D, and go to W6.

W5.6. Weigh D vs E vs F+1. (8 permutations left.)

• If D is lightest, go to W6.
• If E is lightest, swap D<->E, and go to W6.
• If F+1 is lightest, cyclically relabel B->F->E->D->C->B, and go to W6.
• If no pan is lightest, swap B<->C, cyclically relabel D->F->E->D, and go to W6.

W6. Weigh D+2 vs E vs F. (2 permutations left.)

• If E is lightest, the weight order is A,B,C,D,E,F.
• If F is lightest, the weight order is A,B,C,D,F,E.
• The reason that it's not possible with fewer than two clippings is simpler than that: there's no possible weighing that can distinguish the two heaviest balls (assuming it's not allowed to weigh objects other than the balls and clippings). – f'' Jun 22 '15 at 10:11
• @f'' Didn't see it was that easy. :-) I'll incorporate it into my answer. – Christian Semrau Jun 23 '15 at 19:32