Especial de subdivisión de los números del 1 al 99

Question

He estado últimamente trabajando en un problema que todavía no se puede resolver. El problema es:

Podemos dividir los números del 1 al 99 en 33 grupos de tres números, de tal manera que en cada grupo de un número es la suma de los dos elementos restantes?

Gracias de antemano por cualquier ayuda o indicación :)

Answer 1

Si funciona para $n$ entonces funciona para$4n$$4n+3$. Esto puede ser visto de la siguiente manera: suponga que trabaja para $n$, entonces funciona para los números pares hasta que $2n$ (sólo multiplicar todo por 2). Ahora tomamos las combinaciones $(2n+1)+(2n+2)=4n+3, (2n-1)+(2n+3)=4n+2, (2n-3)+(2n+4)=4n+1, \ldots, 1+(3n+2)=3n+3$ Los únicos números que no uso son los números pares hasta que $2n$.

Un análogo argumento demuestra que funciona para $4n$ si funciona para $n$.

user7530 afirma que funciona para$n=24$, por lo que si nos muestra las combinaciones que tienen una respuesta afirmativa, desde $99=4*24+3$.

(Gracias por mostrar el error en mi respuesta anterior, Dennis. Espero que esto tiene más sentido).

Answer 2

No una respuesta, pero algunos datos numéricos, generado mediante el siguiente código rápido:

#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;
}

Resultados hasta el momento en el que se pega a continuación. El peor caso de tiempo de ejecución es exponencial, por lo que nunca puede llegar a 99, pero voy a mantener esto actualizado, ya que el programa sigue funcionando.

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

Hasta ahora, la respuesta parece ser "sí" cuando $n$ satisface la condición necesaria para que $\frac{n(n+1)}{2}$ es incluso.

EDIT: Aquí está la solución para 24 solicitado por Leen de arriba.

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