6
$\begingroup$

This puzzle was inspired by the one in this posting by Hemant Agarwal.

There are n balls. Their weights are distinct positive integers which sum to W. The balls have the property that, if any one of them is removed, the remaining n-1 balls can be partitioned into two subsets of equal total weight.

n>1. What is the smallest possible value of n? And with n set to this value, what is the smallest possible value of W, and what are the balls' respective weights?

Improve this question
$\endgroup$
2
  • $\begingroup$ Sorry @Rosie F, you aren't suppose to change puzzles after somebody has found and used a loophole, but thanks for the check. $\endgroup$
    – David G.
    Commented Jun 21 at 14:26
  • $\begingroup$ @DavidG. There's nothing inherently wrong with that - it seems reasonable to me to edit a question to clarify intent. (That being said, I believe my solution was genuinely not just a "loophole". A loophole would be something that completely trivializes the question.) $\endgroup$
    – Deusovi ♦
    Commented Jun 21 at 14:41

2 Answers 2

Reset to default
2
$\begingroup$

Well, at first look, either all numbers must be even or all must be odd. If this is not the case, some partial sums will be even and some odd, and no partial sum may be odd (since we have to partition to half that size).

Considering the all even case, the weights can all be divided by two to get another solution, so we can omit the all even case.

I assumed non-negative weights of balls.

At this point, I wrote a program to test it... Trying n=5, I found no possible solutions if the largest ball is <100.
Trying n=7, the solutions just poured out. The first is:

13, 11, 9, 7, 5, 3, 1
making W=49

Partitioning as:

11+7 = 9+5+3+1 = 18
13+5+1 = 9+7+3 = 19
13+7 = 11+5+3+1 = 20
11+9+1 = 13+5+3 = 21
13+9 = 11+7+3+1 = 22
13+9+1 = 11+7+5 = 23
13+11 = 9+7+5+3 = 24

Edit, missing part: There cannot be a solution with n even because, after it is minimally reduced, this implies that there are an odd number of odd weights on one side, and an even number of odd weights on the other.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Correct! That was the smallest solution I found, too. $\endgroup$
    – Rosie F
    Commented Jun 21 at 14:25
  • 1
    $\begingroup$ But why can there be no solution with fewer balls? (I read the question as minimal $n$ having priority over minimal $W$.) $\endgroup$
    – Tim Seifert
    Commented Jun 21 at 15:16
  • $\begingroup$ @TimSeifert I think 2, 4, 6 are addressed, 3 is obvious. 5, the issues is that you must achieve 3 balls =1ball at least once and and combine the 1 ball with another in a 2b=2b form. I know it can't be done if the largest ball is < 100. I'm not sure how to rigorously prove it. $\endgroup$
    – David G.
    Commented Jun 21 at 15:25
  • 3
    $\begingroup$ Okay 5 is impossible: (On mobile right now, so sorry if this is a bit messy) Label the Balls ABCDE in increasing weight. Leaving out E forces the split AD-BC (the only other option ABC-D leaves nothing to balance with E once D is omitted). Thus, when we leave out D, we must have the split ABC-E (since BC cannot even reach E alone). When leaving out C, this implies the split AE-BD (as E and D cannot go together and ABD is too large). Finally this is a contradiction with leaving out B, as the same argument gives AE-CD, which conflicts with the previous. $\endgroup$
    – Tim Seifert
    Commented Jun 21 at 15:42
  • $\begingroup$ (I would love to see a less grindy argument though, if anyone comes up with one.) $\endgroup$
    – Tim Seifert
    Commented Jun 21 at 15:46
2
$\begingroup$

It's possible with

5 balls

and here's why:

Give the balls weights -3, -1, 1, 3, 5.
If -3 is removed: -1 + 5 = 1 + 3
If -1 is removed: 5 + -3 + 1 = 3
If 1 is removed: -3 + 5 = -1 + 3
If 3 is removed: 5 + -3 + -1 = 1
If 5 is removed: -3 + 3 = -1 + 1

This is optimal:

All balls must have the same parity, as the proof of the original problem shows.
If the parity is even, we can divide it by 2 to get a smaller-in-absolute-value solution. So let's assume the parity is odd - then there must be an odd number of balls total, so we get an even number when we remove any ball.

1 ball is prohibited by the problem statement. So the only option remaining is 3: is there a 3-ball solution?

Call the three balls' weights $a$, $b$, and $c$. Say we remove $c$. Our only options to balance the scale are "$a$ vs. $b$" and "$a+b$ vs. (nothing)". The first would cause $a=b$, so it must be the second. And of course, the same works for the other two pairs.

But now $a$, $b$, and $c$ all need to have opposite signs from each other. This is impossible, so there is no solution with 3 balls.

It is also optimal in terms of W...

at least, if W is meant to be the sum of absolute values of the weights (which I believe is the natural metric if we're including negative-weight balls).

Improve this answer
$\endgroup$
7
  • $\begingroup$ I believe a 5-ball solution isn't possible if we're limited to positive numbers, but I haven't fully proven it. $\endgroup$
    – Deusovi ♦
    Commented Jun 21 at 14:21
  • 1
    $\begingroup$ think you can add in that $1,3,5,7,9,11,13$ is a valid construction if you require the weights to be positive, was going to write an answer but nevermind ig. $\endgroup$
    – Culver Kwan
    Commented Jun 21 at 14:21
  • $\begingroup$ @CulverKwan That seems worth an answer to me! $\endgroup$
    – Deusovi ♦
    Commented Jun 21 at 14:23
  • 2
    $\begingroup$ I can't accept negative numbers as weights. Your arithmetic looks OK but the problem is about weights of things, and that implicitly implies that they are not negative. Agarwal's original problem didn't explicitly state that the weights had to be positive, but nobody quibbled and none of those that answered entertained the possibility of weights of opposite signs. Nonetheless, I will insert a clarification into the question. $\endgroup$
    – Rosie F
    Commented Jun 21 at 14:23
  • $\begingroup$ @RosieF I think it's perfectly fine to have some of the balls be, say, filled with helium. I realize that it probably wasn't your intention, but it's not like it's meaningless/impossible (like a complex number weight would be) - it's definitely a thing that could physically exist. (And all of the proofs in the original problem did work for negative weights, too!) $\endgroup$
    – Deusovi ♦
    Commented Jun 21 at 14:33

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.