El arte de programar

Imagen de César

Este post es un "entretenimiento" para los que os gusta darle a la sesera...

Supongamos que nos piden que, dados 10 números enteros entre 0 y 100, formemos con ellos dos conjuntos distintos que sumen lo mismo.

Por ejemplo, dados {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, es claro que {1, 2} suma lo mismo que {3}, o que {2, 3, 4, 6} suma lo mismo que {7, 8}.

Hasta aquí la cosa es fácil. Me hago este programita para encontrar dichos subconjuntos (¡pruébalo!):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int main(int argc, char *argv[])
{
    assert(argc==11);

    int i=0;
    int num[10];
    for(i=1; i < argc; i++)
    {
        sscanf(argv[i], "%d", &num[i-1]);
        assert(0 < num[i-1] && num[i-1] < 100);
    }

    int c[10] = {1,0,0,0,0,0,0,0,0,0};
    i=0;
    while (1)
    {
        if (c[i] > 2)
        {
            int j;
            for (j=i; j<10; j++)
            {
                if (c[j]>2)
                {
                    c[j]=0;
                    c[j+1]++;
                }
            }
            i=0;
            continue;
        }

        int s1=0, s2=0;
        int j;
        for (j=0; j<10; j++)
        {
            switch (c[j])
            {
            case 1: s1 += num[j]; break;
            case 2: s2 += num[j]; break;
            }
        }
        if ( s1 == s2 )
        {
            char str1[64], str2[64];
            for (j=0; j<10; j++)
            {
                switch (c[j])
                {
                case 1: if (strlen(str1) > 0 )
                        sprintf(str1, "%s + %d", str1, num[j]);
                    else
                        sprintf(str1, "%d", num[j]);
                    break;
                case 2: if (strlen(str2) > 0 )
                        sprintf(str2, "%s + %d", str2, num[j]);
                    else
                        sprintf(str2, "%d", num[j]);
                    break;
                }
            }
            printf("%s = %d\n", str1, s1);
            printf("%s = %d\n", str2, s2);
            exit(0);
        }

        c[i]++;
    }
}


El problema que os planteo es:
Demostrar que ese while(1) no es un bucle infinito.

(Post dedicado a: Señoras que no saben distinguir entre programar y picar código.)

Comentarios

Imagen de etfiat

...así que el problema a resolver es demostrar que no hay una lista de 10 números naturales inferiores a 100 que no contengan, al menos, un elemento que sea suma del resto.

vamos a intentar encontrar una lista que cumpla eso, partimos de 1

1

el siguiente no puede ser uno porque 1 = 1, por tanto tomamos el 2

1 2

el siguiente no puede ser 3 porque 1 y 2 suman 3

1 2 4

La serie comienza a ser familiar :D

1 2 4 8 16 32 64 ... nos pasamos de 100 ahora nos toca generalizar...

si lo miramos en binario vemos que no quedan "huecos" y con los números de esta serie se pueden construir todos los anteriores.

00000001
00000010
00000100
00001000
00010000
00100000
01000000

El problema se reduce a encontrar una matriz de rango 10 usando vectores de rango inferior a 8 (cosa imposible) por tanto el algoritmo siempre termina.

¿comentarios?
¿aplausos?

Imagen de César

Lo primero, antes de que nadie me lo eche en cara, es que el programita tiene un fallo: por ahorrarme la comprobación de que s1 y s2 no fuesen simultáneamente cero (i.e. ambos conjuntos vacíos), inicialicé c a {1,0,0,0,0,0,0,0,0,0}. Con esto, el bucle acabaría a ir a comenzar de nuevo a comprobar todos los subconjuntos posibles y fuese s1==s2==0. Así que dadlo por corregido, y esta solución no vale. Cambiad mentalmente el s1==s2 por (s1 == s2 && s1 != 0).

Lo segundo, es que tu razonamiento falla en que no partimos de los 100 números, sino de 10 números entre 0 y 100. El 1, 2, 4...64 no tienen porqué estar en ese conjunto. Tienes que demostrar que, dado cualquier conjunto de 10 números entre 0 y 100, siempre se cumplirá la condición y, por tanto, saldremos del bucle.

Imagen de etfiat

Supongamos los 10 números enteros cualesquiera en binario de tamaño byte(de 8 bits):

xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx

Esta matriz por definición tiene un rango máximo de 8, es decir, al menos dos filas son combinación lineal del resto, como estamos en base 2 combinación lineal=suma

he usado 1 2 4 8 16 por ser una base trivial lo mismo se puede aplicar a

00000011
00000110
00001100
00011000
00110000
....
....
....

En definitiva nunca encontraremos 10 vectores linealmente independientes en el rango 0-100 porque ese rango es un espacio 7-dimensional

Igual no era tu intención pero el álgebra explica perfectamente el problema. :D :D

Imagen de César

Toda suma es una combinación lineal, pero no toda combinación lineal es una suma.
Contraejemplo:
Supongamos 4 números enteros cualesquiera en binario:
xxx
xxx
xxx
xxx
Esta matriz tiene un rango máximo de 3, es decir, etc, etc.

Por ejemplo: 3 (011), 5 (101), 6 (110) y 7 (111).
Alguno será combinación lineal del resto: cierto. P.ej: 2·111 = 110 + 101 + 011
Ahora encuentreme usted la suma, pq yo no la veo... :-)

Es decir, según tu razonamiento si tomamos 4 números entre 0 y 8 (exclusive), deberíamos poder encontrar siempre dos subconjuntos con la misma suma, ya que se pueden expresar en base 2 con 3 bits. Sin embargo, yo diría que hay al menos 6 de esos subconjuntos cuya suma es distinta a la de cualquier otro subconjunto.

Imagen de etfiat

Al no permitir la resta si cambias unos por ceros la cosa no funciona.

Lo miro desde otro ángulo, me da la impresión de que el limitar la resta simplemente hace necesaria otra dimensión pero hay que repensarlo un poco.