1

We are given a multi-set of numbers which consist of "$x$" 1's, "$y$" 2's and "$z$" 3's.

Given x,y and z , how to figure how out if this set can be divided into 2 equal parts(where sum of both the sets is equal to each other) ?

Example:- x=1; y=1; z=1; Set is:-{1,2,3} And 2-parts:-->{1,2},{3}

2 Answers2

0

Note that the total sum obviously has to be even. When even, the total number of $x$s and $z$s are even. If the number of $x$s are even, then so are the number of $z$s.

We then consider two cases:

  1. $y$ is even: Split everything evenly.
  2. $y$ is odd: If the number of $x$ is $0$ but not $z$, if we have at least $3$ $y$s, this is clearly possible by distributing evenly all but $2$ $z$s and $3$ $y$s, and then placing them on one side, with the $3$ $y$s on the other. Otherwise, this is clearly not possible. If there are $0$ $z$s but non-zero $x$s, then we can partition the sets by balancing the odd $y$ with $2$ $x$s. If we have zero $x,z$s, its not possible to partition. In all other cases, place $1,2$ on one side, $3$ on the other, and now we are reduced to the case where the number of $x,z$s are odd, and $y$s are even.

If the number of $x$s are odd (and likewise for $z$), we also have two cases:

  1. $y$ is even: If $y$ is $0$, balancing the sets can only happen if there are at least $3$ $x$s, in which case we place $3$ $x$s on one side, $1$ $z$ on the other, then split evenly. Otherwise, place $1,2$ on one side, $3$ on the other, and reduce to the odd $y$, even $x,z$ case.

  2. $y$ is odd: Place $1,2$ on one side, $3$ on the other, and reduce to the even $y$, even $x,z$ case.

In conclusion, if there are an even number of $x,y,z$s, or an odd number of each, the sets are partitionable. I'll leave the rest of the casework to you.

Rushabh Mehta
  • 13,663
0

You can reduce the problem in various ways. For example if you have two digits the same, and take them away and solve the smaller problem you can simply put one back in each set and you are done.

Note the number of ones plus the number of threes must be even.

So you can reduce by removing any of $$\{1, 1\}; \{2, 2\}; \{3, 3\}; \{1, 1, 2\}; \{1, 1, 1, 3\}; \{1, 2, 3\}; \{1, 2, 2, 3\}; \{2, 2, 2, 3, 3\}$$

Note that this means you can take out a single $1$ and $3$ and any non-zero number of twos.

Now you can adopt the following strategy.

Take out pairs of ones and pairs of threes. You either end up (a) with only twos, or (b) with a one, a three and possibly some twos.

In (a) if you end up with an even number of twos, you can split them and are done.

In (b) if you have any twos left you are done.

So the problem cases are an odd number of twos in case (a) - that means you started with an odd number of twos. If you began with at least two ones, you can take out a single two, using $\{1,1,2\}$ and if you began with at least two threes you can take out three twos with $\{2,2,2,3,3\}$. Can you spot any cases you can't deal with?

Then in case (b) you may have a problem if you had no twos to start with. If you started with at least three ones you can take out $\{1,1,1,3\}$ and change the parity of the ones and threes. Are there any cases you can't deal with here?

For cases where the sum is even, this should lead you to conclude that the bad cases are: an odd number of twos with no ones or threes (one set has sum divisible by four, the other doesn't); a single one and an odd number of threes (one set has a sum divisible by three and the other doesn't); a single two and an even number of threes (one set sum divisible by three). In all other cases the reduction shows that the problem can be solved.

Mark Bennet
  • 100,194