Rompecabezas | los simbolos

Hay dos puertas. Uno va al infierno y el otro al cielo. El portero le hace un rompecabezas a Sahil para decidir qué puerta debe abrirle. Obviamente, si Sahil responde correctamente el acertijo, la puerta al cielo se abrirá, de lo contrario, la puerta al infierno. De acuerdo con el problema, a Sahil se le dan n enteros consecutivos del 1 al n, que se escriben en una fila. Tiene que poner los signos «+» y «-» delante de ellos para que la expresión obtenida sea igual a 0 o, si la tarea es imposible de hacer, entonces Sahil debe decirle al guardián «No existe solución para el problema dado». El guardián espera que Sahil encuentre su respuesta en un tiempo mínimo utilizando un enfoque eficiente en lugar de examinar todas las formas posibles de colocar las señales. Sahil viene a ti considerándote como su amigo. ¿Le ayudarías a llegar a la solución?

Solución:
El acertijo tiene solución si y solo si n o n+1 es divisible por 4.

Explicación:
el problema es equivalente a dividir n enteros de 1 a n en dos subconjuntos disjuntos con la misma suma. Los subconjuntos disjuntos son los subconjuntos que no tienen ningún elemento común. Los dos subconjuntos disjuntos serán:
1) un subconjunto de números con un signo más delante de ellos, y
2) un subconjunto de números con un signo menos delante de ellos.

Dado que la suma de los primeros n enteros consecutivos es S = 1 + 2 + 3 + —————— + n = (n)(n + 1)/2, la suma de los números en cada uno de los subconjuntos debe ser igual a exactamente la mitad de S, es decir, S/2. Significa que el valor de S, es decir, (n)(n+1)/2 debe ser par para que el rompecabezas tenga solución.

Acercarse :

1) Está claro que n(n + 1)/2 es par si y sólo si n es múltiplo de 4 o n + 1 es múltiplo de 4.

2) De hecho, si n(n + 1)/2 = 2t, esto implica que n(n + 1) = 4t, y como n o n + 1 son impares, el otro debe ser divisible por 4. Por el contrario, si ya sea n o n + 1 es un múltiplo de 4, y por lo tanto n(n + 1)/2 es obviamente par.

3) Ahora, considerando el caso cuando n es divisible por 4. En este caso, podemos, por ejemplo, dividir la secuencia de números enteros de 1 an en n/4 grupos de cuatro números enteros consecutivos y luego poner el signo «+» antes del el primer y cuarto número y el signo “-” antes del segundo y tercer número en cada uno de estos n/4 grupos. Esto se puede entender como:

(1 – 2 – 3 + 4) + (5 – 6 – 7 + 8) + ———— + ((n – 3) – (n – 2) – (n – 1) + n) = 0. — ——–(1)

4) Ahora considerando el caso cuando n + 1 es divisible por 4, entonces n = 4t – 1, lo que implica n = 3 + 4(t – 1), y podemos explotar la misma idea ocupándonos primero de los tres primeros números de la siguiente manera:

(1 + 2 – 3) + (4 – 5 – 6 + 7) + ———— + ((n – 3) – (n – 2) – (n – 1) + n) = 0. ——— –(2)

Para resumir, el problema tendrá las siguientes soluciones:
Calcule n mod 4, es decir, el resto de la división de n entre 4.
Solución 1: Si el resto es igual a 0, inserte los signos «+» y «-» como indicado por la fórmula (1).
Solución 2: Si el resto es igual a 3, inserte los signos «+» y «-» como lo indica la fórmula (2).
De lo contrario, devuelve el mensaje «No existe solución para el problema dado».

Referencia: Rompecabezas algorítmicos – Anany Levitin, Maria Levitin