2. Estrategias para Resolver Problemas
En este capítulo no se pretende dar un conjunto de reglas
fijas para resolver problemas tipo olimpiada, sino exponer unas estrategias
sencillas, ilustradas con ejemplos, que se aplican en diferentes casos.
Seguiremos el convenio de poner el enunciado de los ejemplos ó problemas en
negrita.
2.
1. Estrategias Básicas
Pensemos en el siguiente problema:
Tenemos un aro, alrededor del cual hemos escrito nueve
números, que son 1 ó 0. No todos ellos son 1 ni todos ellos son 0. Entonces, en cada paso
escribimos, entre cada dos números un 1 si los dos números son iguales o un 0
si los dos números son distintos, y luego borramos los números que teníamos al
principio. ¿Es posible, en un número finito de pasos, conseguir que los nueve
números sean 1?
(Propuesto en [2])
En un principio el problema puede parecer muy complicado,
pero supondremos que tenemos el problema resuelto, y veremos qué pasa antes. Si
hemos llegado a tener todo 1, es porque en el paso anterior todos los números
eran iguales, es decir, teníamos nueve ceros. Sin embargo, para tener nueve
ceros, en el paso anterior teníamos que tener todos los números alternos, ya
que tenían que ser distintos cada dos. Esto es, teníamos que tener 1, 0, 1, 0,
1, 0, 1, 0, 1, y vemos que por ser nueve un número impar, el noveno número y el
primero son 1, entre ellos se pondría un 1, por lo que es imposible obtener 9
ceros , así que es imposible también llegar a tener nueve unos.
A esta estrategia se la conoce como trabajar hacia atrás, y
como hemos visto consiste en suponer que hemos llegado a la situación que nos
piden, y a partir de ahí vamos viendo qué ocurría en situaciones anteriores, lo
que nos puede llevar a que la situación pedida es imposible, darnos condiciones
para que se cumpla, etc.
Otra estrategia muy conocida
es buscar cosas que no cambien, sobre todo en procesos iterativos. La
explicaremos también con un ejemplo:
Sea n un número impar. Escribimos en una pizarra los números del 1 al 2
n. A cada paso podemos escoger dos
números cualesquiera de la pizarra, 
y 
, borrarlos y escribir en su lugar 
. Demostrar que al final del proceso siempre quedará en la
pizarra un número impar.
Buscaremos alguna propiedad que no cambie al repetir el
proceso. Por ejemplo, es fácil ver que la paridad de la suma no cambia al
borrar dos números y sustituirlos por su diferencia, ya que
,
y puesto que la diferencia será 
(si 
) ó 
(si 
), 
ó 
tendrá la misma
paridad que 
.
Veamos cuánto vale : 
que es impar por
ser n impar. Por tanto, cuando quede
un solo elemento v, 
y es impar,
por tanto, v ha de ser impar.
Vemos por último en este apartado otras formas de demostrar muy
conocidas como son la reducción al absurdo y el principio de inducción. La
reducción al absurdo consiste en suponer que lo que nos piden demostrar no se
cumple (es falso) y llegar a una contradicción. El principio de inducción, sin
embargo, nos permite probar que una propiedad es cierta para un conjunto
numerable si ésta es cierta para un cierto elemento 
que sea el mínimo
del conjunto. Consiste en demostrar
que es cierta para y luego en probar que
si es cierta para un número n,
también es cierta para el siguiente n+1.
Hay alguna variante de la inducción, por ejemplo probar que una propiedad es
cierta para r números 
y luego probar que si
la propiedad es cierta para n,
también se cumple para 
, ó demostrar que si se cumple para un número n y todos los anteriores también se
cumple para n+1.
Como ejemplos podemos pensar
en los siguientes problemas:
Reducción al absurdo:
Un grupo de diez amigos va a un
restaurante a comer. Al final de la comida, el camarero les trae la cuenta, de
un total de 225 euros. Prueba que podemos escoger dos de ellos de modo que
entre los dos pagarán al menos 45 euros.
Supongamos que no, esto es, que es imposible escoger a dos de
ellos con esta propiedad. Entonces, hagamos cinco parejas al azar, de modo que
todos estén en una pareja. Como entre todos pagaron 225 euros, 
donde 
es el dinero que
pusieron en total los dos amigos de la pareja i. Hemos supuesto que cada pareja paga menos de 45 euros, y por
tanto 
, lo que contradice a que en total pagaron 225 euros. Por
tanto siempre podemos escoger una pareja con la propiedad pedida.
Inducción:
Demostrar
que 
Vemos que la propiedad es cierta para 
, ya que 
.
Supongamos que es cierta para 
. Entonces para 
tenemos que
, y
queda demostrado.