13
$\begingroup$

I've been lately working on a problem I still can't solve. The problem is:

Can we divide numbers from 1 to 99 into 33 groups of three numbers, such that in every group one number is the sum of the two remaining elements?

Thank you in advance for any help or indication :)

$\endgroup$

3 Answers 3

10
$\begingroup$

If it works for $n$ then it works for $4n$ and $4n+3$. This can be seen as follows: assume it works for $n$, then it works for the even numbers until $2n$ (just multiply everything by 2).

Now we take following combinations: $(2n+1)+(2n+2)=4n+3$, $(2n-1)+(2n+3)=4n+2$, $(2n-3)+(2n+4)=4n+1$, $\ldots$, $1+(3n+2)=3n+3$.

The only numbers we did not use are the even numbers until $2n$.

An analogous argument shows that it works for $4n$ if it works for $n$.

user7530 has shown that it works for $n=24$ in another answer, so we have an affirmative answer, since $99=4*24+3$.

(Thanks for showing the error in my previous answer, Dennis. I hope this one makes more sense.)

$\endgroup$
6
  • $\begingroup$ (Yeah, this makes more sense. Nice one!) $\endgroup$ Oct 4, 2013 at 23:05
  • $\begingroup$ I've been working on your mathematical analysis Leen..You can't just multiply everything by 2..lot of numbers will repeat..One number can't appear in two groups :) Otherwise, Could you give the final combinations for 99 ? $\endgroup$
    – user99151
    Oct 6, 2013 at 15:28
  • $\begingroup$ @mounmain: [[8,20,28],[6,24,30],[16,18,34],[14,22,36],[12,26,38],[10,32,42],[4,40,44],[2,46,48],[1,74,75],[3, 73,76],[5,72,77],[7,71,78],[9,70,79],[11,69,80],[13,68,81],[15,67,82],[17,66,83],[19,65,84],[21,64,85],[ 23,63,86],[25,62,87],[27,61,88],[29,60,89],[31,59,90],[33,58,91],[35,57,92],[37,56,93],[39,55,94],[41,54, 95],[43,53,96],[45,52,97],[47,51,98],[49,50,99]] $\endgroup$
    – miracle173
    Oct 7, 2013 at 0:52
  • $\begingroup$ @mounaim: multiplying by 2 is a linear operation. If there were no duplicates before the multiplication, there will be no duplicates after the multiplication. Clearly you only have covered even numbers after the multiplication. $\endgroup$ Oct 7, 2013 at 4:30
  • $\begingroup$ @mounmain: I don't know how to access your old acount you should open a question in meta.math.stackexchange.com $\endgroup$
    – miracle173
    Oct 7, 2013 at 21:35
4
$\begingroup$

Not an answer, but some numerical data, generated using the following quick code:

#include <vector>
#include <iostream>
#include <cstdlib>

using namespace std;

void getCandidates(int sum, const vector<bool> &nums, vector<int> &choices)
{
    choices.clear();
    for(int i=0; i<(sum-1)/2; i++)
    {
        if(nums[i] && nums[sum-i-2] && i != sum-i-2)
        {
            choices.push_back(i);
        }
    }
}

bool recurse(const vector<bool> &nums)
{
    int max=-1;
    for(int i=0; i<nums.size(); i++)
    {
        if(nums[i])
            max = i;
    }
    if(max == -1)
    {
        return true;
    }
    vector<int> cands;
    getCandidates(max+1, nums, cands);
    for(int i=0; i<cands.size(); i++)
    {
        vector<bool> copy = nums;
        copy[max] = false;
        copy[cands[i]] = false;
        copy[max-cands[i]-1] = false;
        if(recurse(copy))
            return true;
    }
    return false;
}

void testSize(int size)
{
    vector<bool> nums;
    for(int i=0; i<size; i++)
        nums.push_back(true);
    cout << size << ": ";
    if(recurse(nums))
        cout << "yes";
    else
        cout << "no";
    cout << endl;
}

int main()
{
    for(int i=0; i<33; i++)
        testSize(3*i);
    return 0;
}

Output so far is pasted below. Worst-case runtime is exponential, so it may never get to 99, but I'll keep this updated as the program keeps running.

0: yes
3: yes
6: no
9: no
12: yes
15: yes
18: no
21: no
24: yes
27: yes
30: no
33: no
36: yes
39: yes
42: no
45: no
48: yes
51: yes
54: no
57: no
60: yes
63: yes

So far the answer seems to be "yes" whenever $n$ satisfies the necessary condition that $\frac{n(n+1)}{2}$ is even.

EDIT: Here is the solution for 24 as requested by Leen above.

(14, 4, 10) (15, 3, 12) (17, 8, 9) (18, 7, 11) (19, 6, 13) (21, 5, 16) (22, 2, 20) (24, 1, 23)

$\endgroup$
2
  • 1
    $\begingroup$ A couple observations that might help speed things up: any group of three has to contain either all even or one even and two odd numbers $\endgroup$ Oct 4, 2013 at 19:07
  • $\begingroup$ Of course $n(n+1)/2$ must be even. Each "pod" has a sum of twice the largest element, hence even. $\endgroup$ Jan 12, 2019 at 10:23
0
$\begingroup$

Generalise $n$ and let $n=3m$. This problem is a laxer version of the following more restrictive one:

Partition $\{1, \dots, 3m\}$ into $m$ 3-sets $\{x_i, y_i, z_i\}$, $i=1, \dots, m$, where $x_i+y_i=z_i$ and $y_i\leqslant m$.

This more restrictive problem is equivalent to one studied by Skolem and another studied by Nickerson. Nickerson's problem is in turn a variant of a problem studied by Langford. Nowakowski, ch.1, states these problems, shows equivalences among them, and also gives solutions, for which he cites Davies and Skolem (the latter two citations are taken from the bibliography in Nowakowski).

R. J. Nowakowski. Generalizations of the Langford-Skolem problem. MS Thesis, Dept. Math., Univ. Calgary, May 1975.

R.O. Davies. On Langford's Problem. II, Math. Gaz. 43 (1959), pp.253-255.

T. Skolem. On certain distributions of integers in pairs with given differences. Math. Scand. 5 (1957), pp.57-58; M.R. 19, 1159.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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