Ley de la evolución: el pupilo siempre supera al maestro

Si los hijos no fuesen más inteligentes que los padres y los alumnos no superasen a sus maestros el mundo no avanzaría. Habrá algún escéptico que piense que el mundo no ha avanzado nada en siglos. Quizás haya algo de razón en eso, al menos, en términos relativos. Pero, en general, podemos decir que el mundo ha evolucionado y mucho.
Si queréis una prueba de que los maestros siempre son superados por los pupilos, hela aquí. La he sufrido en mis propias carnes y puedo deciros que produce una sensación muy satisfactoria al mismo tiempo que desconsoladora. En fin, el ser humano es así de paradójico. Resulta que Dani acudió a mí en su momento para ayudarle con la algoritmia. Desde el principio se veía que era un tipo espabilado pero, en el fondo, eso no es la cualidad más significativa para garantizar nada. Lo mejor es que "curraba" un montón en los ejercicios, tanto que no era capaz de seguirle el ritmo a la hora de corregir. Y ya se sabe que va tanto el cántaro a la fuente que acaba por romper. Un día aparece con un ejercicio de examen en el que dos socios intentan repartirse un conjunto de valores de una empresa (o algo así) expresados como enteros positivos. Había que diseñar un algoritmo que comprobase si era posible un reparto equitativo entre los dos socios teniendo en cuenta que los valores no se podían fraccionar. Pues bien, yo le dije que eso se resuelve claramente con Backtracking y refinándolo con una pequeña poda, porque para cualquier solución voraz puede encontrarse un contraejemplo que la deseche. Pero Dani, llevado quizás por la similitud con el problema de la mochila, proponía un algoritmo voraz que primero ordene los valores de mayor a menor y luego vaya tomando los valores uno a uno empezando por la izquierda, añadiendo el valor a la suma parcial si no se pasa de la mitad y descartándolo, en otro caso. Si acabada la lista no ha sido capaz de encontrar un conjunto de valores que sumen exactamente la mitad, es que no se pueden repartir.
Me disponía yo a encontrar rápidamente un contraejemplo que descartara la validez de la solución (como máximo eso suele llevar cinco minutos) cuando descubro asombrado que parece imposible encontrarla, hasta el punto de que me hace dudar y acabo, pasadas las semanas sin hallar contraejemplo alguno, convencido de que el chaval tiene razón. Ya sólo pensaba en una cosa: cómo demostrarlo formalmente.
El colmo de la historia llega cuando hoy, tras varios meses, Dani me envía un e-mail diciendo que efectivamente su algoritmo (el que había puesto mi capacidad como docente de algoritmia en entredicho) no funcionaba porque había encontrado un contraejemplo que lo demostraba. Para los valores 60 40 30 27 15 10 8, la mitad es 95, lo que le tocaría a cada socio. La propuesta voraz de Dani, una vez ordenados los valores en orden decreciente, tomaría el 60, desecharía el 40 porque se pasa, seguiría tomando el 30 - lo que da una suma parcial de 90 (faltan 5) -, desecharía el 27, el 15, el 10 y el 8 porque se pasan y llegaría al final concluyendo que el reparto es imposible, cuando en realidad sí lo es. A saber, por una parte 60+27+8 = 95 y por otra 40+30+15+10 = 95.
¡Imaginaos la cara de tonto que se me quedó! ¡Enhorabuena, Dani! Si tú, con tu tesón, no te mereces aprobar algoritmia no se lo merece nadie.