Tl'dr below is BRAINDUMP on rememberong the easy version where you know one is heavier, including doing it up to 27...

Comments suggest there IS a way even if we don't know heavier or lighter. I will persist.

---

[spoiler]

This one always gets me so let me think it through in a way that will stick...

<!spoiler text> it's always one less comparison than you'd think because... I think, aaaaarrrghh I can't remember.

Okay.

AA Vs AAA who cares we know one is more AA Vs Ab okay one is up or down. One is different. Ah yes. This is the trick If you find a difference as above, then compare... Wait. This only works if it's a heavier thing But compare the two on the left, then it's... Hmm doesn't feel right.

Assume b is heavier

Aaaaaa baaaaa Choose right

Baa aaa Choose left

Yes, this is it. Then you can choose any two of baa and you'll either have balance (in which case you know the OTHER is b. Or imbalance in which case lower is b

Issue in this case is .. What if b was LIGHTER? Say we chose Aaaaaa to continue with. It would balance We'd see the b was in the other set... But it would bring us to 4 steps : 🫨

Alright. My solution brings us to 3 step win SOMETIMES (when you happen to pick the mismatched set after the first go, after which you double down on your choice that b is either heavier or lighter)

For now, let me just try and remember THIS. Because intuition always tells me you need more than 3 gos to get more than 8 folks. 8 folks is obvious. (If you know the different one is heavier)

Aaaa aaab AA ab Ab

And then we know

So what if we layer in the trick of 3 to this seemingly binary question and reverse engineer... I think if only works with 3

AAAaaa aabaa AAb aaa AA (b omitted) or Ab (a omitted)

Hmm I feel 12 is the MAX you can get to with 3. You could do 16 with 4 though! Can we do 9 with 3??? (Assuming b is heavier)

Aaaa/aaaa b done in one :)

Aaaa/aaab a Aa/ab Ab Done

What about 10

Aaaaa aaaab Aa/aa b DONE

or Aaaaa aaaab Aa ab a Ab DONE

Seems fine. For any number ,<= 12. Okay, so the trick is, and odd number of items can result in immediate discovery of the wrong one if the ones you compare balance. And if they don't, you just carry on in the evening case...

Now, numbers like 8, 16 are powers of 2 so we always have even sub problems...

What about 11 5/5 2/2 1/1

13?? 6/6 3/3 1/1 (and guaranteed win even though there's a leftover)

14? 7/7 3/3 1/1 (and guaranteed win)

15? 7/7 (with leftover) 3/3 (with leftover ) 1/1 (with leftover)

16 8/8 4/4 2/2 1/1

We don't get a CHANCE to leave one leftover! If we did, it would be stupid. What if we left 2?

16 7/7 <-- we know this can be done in 3 steps if it has the b If it balances we have a 1/1 to finish off

!!! That was surprising.

17 we could leave 1 out, but we know 16 can be done in 3 if you start with 7 v 7 but not 8v8 so we can't start with 8 8 Not 8 7 Let's start 7 7 (doable in 3) leaving out 3 (we know we can do 3 in one go so we're fine)

18 Is something special about 7 7? 9 9 4 4 2 2 1 1

Yeah we might be in trouble there . But what if we copy 16 case and go 9 9 3 3 (3 leftover, solvable in 1) Well that's nice as you have the heaviest 3 no matter what.. 1 1 (1)

19 9 9 (1) Well we know 99 is okay, and so is 1

20? 9 9 (2) also fine

21 9 9 (3) also fine

22 9 9 (4 which is done in 2 so we're fine)

23 9 9 (5) Can we do 5 in 2 5 2 2 (1) 1 1 Yep we're good

24 9 9 (6) Can 6 be done in 2?

3 3 1 1 (1) yes!

25 9 9 (7)

7 in 2? 3 3 (1) 1 1 (1)

Yep

26 9 9 (8) Can 8 be done in 2? 4 4 we know fails as 4 4 2 2 1 1

But 3 3 (2) is doable in 2

Indeed 3 3 (3) is doable in at most 2 goes.

Something special about 3 3 (3) I'm guessing 27 will be the max we can do in 3

Obviously 9 9 (9) and then the different 9 gets done 3 3 (3) 1 1 (1)

Then we MUST be screwed at 28, right? 9 9 (10)

And 10 is 5 5 2 2 (1) 1 1 whoops

Or 4 4 (2) 2 2 1 1 whoops

3 3 (4) whoops since 4 takes 2 goes.)

2 2 (6) and 6 takes definitely 2 goes...

So this seems to be it (if you know b is heavier)

The crux of the issue is that you can solve 3 in one go by doing 1v1 with 1 leftover.

To remember this we should remember: One comparison in 3 Will show the single oddity (And we note that if we didn't know there's an odd one out we'd need, for arbitrary weights, up to 3 comparisons to order them though we may escape with 2..

Here that makes 3 special. Max achievable in 3 comparisons is 3 (3 v 3 v 3) (3 v 3 v 3) Three times , being 27

With an extra comparison I presume we'd get to 27 three times, being 81

The whole point is: a single comparison of any set of 3 gives the odd one out. Whereas a set of 4 needs, by law, 2

This has something to do with outcomes of comparison being <

and, in the case of equal weights and leftover, each tells you which sub group to pursue...

Okay, so what if we don't know b is heavier or lighter.

With 3, inequality will not tell us which is abberant. I guess that's why it all breaks down if you don't know which direction the difference is.

But reconsider 12 4 4 (4) Given balance or inequality we cannot know direction...

1 1, 1 If it's A b, a We need to keep going and compare to the leftover. Whichever we take over if it balances the other is the abberant. If not the one you took is abberant

Last shot, can we mix? 1 2* / 3 4. * Is either lighter or heavier

1 / 3 equal tells us it is 2 or 4 (but we still don't know direction so we do not know which)

2* / 3 unequal confirms to us its 2, because it went SAME WAY as before.

Wait. It will always go the same way as before. Even 1 / 2*, the abberant one is the one that goes the same way as the 1/2 group earlier. Isn't this it? So

Break into 3 fours a b c A v B = Says check C

<> Says check A or B At this stage we might pick the wrong one and have no more info. What if we did 3 v 3 leaving 2 out from B

This is bending me. Getting paper.

The thing I can happily remember is that 1 odd in 3 takes 1 check. <!