2
$\begingroup$

This problem is a generalization of Twelve balls and a scale problem. So I can solve and understand how things are going if we have 12 balls or 9 balls but how do I generalize? If say we have $3^n$ balls, then how many measurements will it take given

  1. we know the odd-man-out ball is heavier or lighter
  2. we don't know if the odd-man-out ball is heavier or lighter

For the first question, I believe the answer to be n measurements since at each stage we eliminate 2/3 of the total balls available so I guess I am able to justify this. But what about the part 2, I really have no clue. This tells us the strategy but how do we even come up to the answer? I mean the intuition behind the answer. Do you just check examples and guess a pattern? Or is there a structured approach to this problem?

$\endgroup$
2
  • 1
    $\begingroup$ How is this question distinct from the generalized one you link? Or are you just asking for explanation of the answers given there? If so, what exactly do you want explained? $\endgroup$
    – bobble
    Jul 7, 2022 at 20:13
  • $\begingroup$ @bobble I meant the intuition behind the answer? Did you just check examples and guess a pattern? Or is there a structured approach to this problem? $\endgroup$
    – Charlie
    Jul 8, 2022 at 15:41

1 Answer 1

1
$\begingroup$

For case #1, your claim is correct that for $3^n$ balls, the heavier (or lighter) one can be found in n weighings, assuming we know that the odd ball is either lighter or heavier.

For case #2, where we do not know if the odd ball is heavier or lighter, we can find the odd ball and tell whether it is heavy or light in a group of

$((3^n)-3)/2$ balls with n weighings.

That is 3 balls with 2 weighings, up to 12 balls with 3 weighings, up to 39 balls with 4 weighings, up to 120 balls with 5 weighings, and so on.


EDIT:
In reply to your comment asking for an explanation...

Let's take the simplest possible example as an illustration: the case where we have 3 balls and we need 2 weighings to guarantee that we can determine both the odd ball and whether it is heavier or lighter.

First, let's try to pinpoint the confusion so we can better dissolve it.

When we know that the odd ball is heavier (and also when we know that the odd ball is lighter) we can find the odd ball for $3^n$ balls with just n weighings, as you said in your post. When we don't know whether the odd ball is heavy or light, we need to set up the weighings so that each possible set of placements and its inverse is distinct.

Therefore, we lose half of our possible placements at the very least. At first it seems to logically follow that we could weigh up to half the number of balls when we don't know whether the odd ball is heavy or light, compared to when we do know if it's heavy (or light).

The example below will hopefully show why that is never true, and why "$((3^n)-3)/2$ balls with n weighings" is true when we don't know whether the odd ball is heavy or light AND we want to guarantee being able to find the odd ball and whether it is heavy or light.

Here is the setup:
enter image description here
enter image description here

At this point, maybe you are thinking, "Why can't we weigh 4 balls in 2 weighings, since in the case where we know the odd ball is heavier, we can weigh $3^n$ balls, which is $9$ balls when $n=2$, and half of $9$ is $4.5$? Also, we have $3$ placements of the $9$ available that we haven't even used: ==, LL, and RR. Why can't we use them?"

Here's Why:

As Joe Z (user88) explained in the link in your post, we would then be forced to put an odd number of items on the scale, and that won't work. Check out the row highlighted in pink below, where I've tried to add in a 4th ball.
enter image description here
enter image description here

Does this help explain it better? Maybe the visuals help? This behavior holds true for all n, meaning that even though there are a few mappings left over that we haven't used, we cannot use them to add another ball.


Now, with all that said, I want to make a separate but relevant point.

As Joe Z said in his answer to his "12 balls in 3 weighings" puzzle, one could add a 13th ball that is never weighed, and if all of the weighings were "=", then the odd ball is that 13th one, but one cannot know if it is heavy or light without 1 more weighing.

However, realize that that means that if you have 13 balls and perform just 3 weighings, $100$% of the time you will find the odd ball, and $12/13$% of the time you will find whether that odd ball is heavier or lighter. Only in the $1/13$% case where the un-weighed ball is the odd ball will you be unsure if the odd ball is heavier or lighter.

As the number of balls and weighings increase, the % chance of the un-weighed ball being the odd ball decreases, meaning that one is more and more likely to be able to weigh $(((3^n)-3)/2)$ + 1 balls with n weighings, but it is never guaranteed.

I welcome any and all corrections to anything in this post.

$\endgroup$
4
  • $\begingroup$ Hey, can you explain how did you get (3^n -3)/2? That is precisely my question. $\endgroup$
    – Charlie
    Jul 8, 2022 at 15:40
  • $\begingroup$ @Charlie I think the heart of it is in Joe Z's (now User88's) answer: "We can't use LLL and RRR as a 13th pair for a 13th ball, because then we'd end up having to put nine balls onto the scale, and there's no way to do that since nine is odd. We could probably use it in place of one of the LLR/RRL pairs, but leaving LLL and RRR out makes for a symmetry in the result chart that I rather like." (continued) $\endgroup$
    – JLee
    Jul 8, 2022 at 17:02
  • $\begingroup$ @Charlie "However, what's interesting is that you can have a 13th ball that you never place on any scale, and if your scales balance out in all three weighings, the 13th ball you never weighed is the odd ball out (although you obviously can't tell without a fourth weighing whether it's lighter or heavier)." I will add in a thorough explanation. $\endgroup$
    – JLee
    Jul 8, 2022 at 17:03
  • $\begingroup$ @Charlie Ok, I added in an explanation. i hope it helps. $\endgroup$
    – JLee
    Jul 8, 2022 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.