0
$\begingroup$

I'm trying to solve a riddle but not sure how to go about it. Here goes. There are ten groups of identical objects. Each group has one more then the last. So in other words the first group has one object, the second group has two objects, and so on. Someone comes along and combines all the groups into two piles. Pile "A" has 42 and pile "B" has 13. Which groups were combined to create pile "A" and which groups were combined to create pile "B". A possible solution to this is as follows.

"A" = [2,3,4,6,8,9,10]

"B" = [1,5,7]

I have three main questions relating to this.

  1. Are there other possible solutions to this question? I hope not. :)

  2. It seems like there should be a way to do this algebraically. Is there?

  3. This question is the most important. Is there a way to solve this same problem on a larger scale? let's say you were given the same problem but there were 1,000 or even 1,000,000 groups. I'm looking for a way to solve this larger scale issue with only one solution. If that's not possible to do as is than it's OK to add a variable before the piles get combined. I'm not sure if that would even help but it's within the constraints of this question if needed.

I'm also not really sure what tags to apply. So if there is a tag that should or should not be tagged here please let me know.

$\endgroup$
8
  • $\begingroup$ $13$ may be the sum of $\{ 10,3 \}$, $\{ 9,4 \}$, $\{ 8,5 \}$, $\{ 7,6\}$, $\{ 10,1,2 \}$, and many others. The solution is not unique. $\endgroup$
    – Crostul
    Nov 5, 2016 at 2:29
  • 2
    $\begingroup$ I think neither algebraic geometry nor abstract algebra should be tags. $\endgroup$
    – Xam
    Nov 5, 2016 at 2:31
  • $\begingroup$ Cool I'll remove them. $\endgroup$
    – Kahless
    Nov 5, 2016 at 2:31
  • $\begingroup$ Why do you think that if elements in Group B are summed to be 13 (in a certain way) group A elements would not sum up to 42? $\endgroup$
    – Thanassis
    Nov 5, 2016 at 2:34
  • $\begingroup$ You say that "Each group has one more then the last". Then you say "in other words the first group has one, the second group has two, and so on". This does not follow from your description. You have to add that the first group has 1 element. $\endgroup$
    – Thanassis
    Nov 5, 2016 at 2:38

3 Answers 3

1
$\begingroup$

The fact that there are ten groups and the total of the piles is $55$ says the groups start at $1$ and end at $10$. The sum of the numbers from $1$ to $10$ is $\frac 1210\cdot 11=55$, the tenth triangular number. There are many collections from that set that add to $13$. For a larger total number you can repeat the triangular number calculation. For example, if you say the same with $\frac 12200\cdot 201=20100$ you could say there are $200$ piles with a total of $20100$ objects, which forces the piles to be from $1$ to $200$. Then if you require that you use $10$ piles to get $55$ objects you have a unique solution.

$\endgroup$
2
  • $\begingroup$ Thanks for telling me about triangular numbers. I just took a look at the Wiki you linked and it's supper cool. I get the formula for calculating the total number of objects but I'm not sure how this can result in a unique solution. Can you please explain a bit further. $\endgroup$
    – Kahless
    Nov 5, 2016 at 6:22
  • $\begingroup$ The triangular number is the smallest the sum of that many numbers can be. If you want ten different numbers, the smallest the sum can be is $55$, which is what makes that unique. If you change any number, the new number has to be at least $11$ and the sum will increase. You can still have uniqueness with one more. If you ask for ten numbers that sum to $56$, it has to be $1-9$ and $11$. Any higher and you have too much slack for uniqueness as $57$ could be $1-9$ and $12$ or $1-8, 10, 11$ $\endgroup$ Nov 5, 2016 at 14:03
0
$\begingroup$

Since there are groups of every natural number initially, there are multiple solutions to the problem. The number of solutions is the number of ways of partition of 13, because once you make a,pile of 13, the rest pile up to 42. So you can take the smallest pile and calculate the number of partitions of smallest number. This is arithmetic, no. Of partitions, you could see the numberphile video on YouTube, and by adding number of constraints, only one solution or no solution can be obtained. For larger numbers, the constraints will have to be more.

$\endgroup$
0
$\begingroup$

First of all you do not have to look at this problem as groups of identical elements. I do not think it adds anything to the nature of the problem. The problem essentially asks: You have numbers $1,2,...10$. Partition the numbers in two groups A and B, so that the sum of A is $42$, and the sum of B is $13$.

We notice that the sum of the first $10$ numbers is $(10\times 11)/2 = 55$. So the sums of the two partitions should add up to $55$. If they do not, then we know there is no solution. In our case they do, so there might be a solution. If we make one group with one of the correct sums, then the other falls into place (it has the other sum).

To answer your questions:

  1. Yes, there are many other solutions. It is easier to look at the group with the smaller sum, and try to find solutions for it. Your solution of $\{1,5,7\}$ is a valid one and in total there are 15 solutions: $\{10,3\}, \{10,2,1\},\{9,4\}, \{9,3,1\},\{8,5\}, \{8,4,1\},\{8,3,2\},\{7,6\},\color{red}{\{7,5,1\}},\{7,4,2\},\{7,3,2,1\},\{6,5,2\},\{6,4,3\},\{6,4,2,1\},\{5,4,3,1\}$

  2. Yes, you can solve this problem in a systematic way. There is really no algebra involved, so I would not call the solution algebraic. But you can come up with an algorithm that given a partition of the sums it returns the number of solutions and the solutions. Do you want to give it a try? Take some hints in the way I have listed the $15$ solutions for the $(13,42)$ partition. I can post my effort afterwards.

  3. An algorithm for the case of $1...10$ should also work for the case $1...1000$, so you will have your answer there. This assumes that you want to solve the equivalent problem. If you are asking for a solution to a slightly different problem, for example: you have a set $S$ that is not necessarily $\{1,2,...n\}$ and you want to partition S to two other sets with sums of X, Y, then this is a Integer Linear Programming problem and we know these are NP-hard problems (in layman's terms, there is no algorithm to solve these problems fast, i.e., in polynomial time)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .