Connaissant les faiblesses de Superman (la Kryptonite et la combinatoire), Lex Luthor lui soumet le maléfique problème suivant.
Devant lui, Superman dispose d'une sorte de plateau allongé contenant plusieurs emplacements alignés. Le nombre réel d'emplacements est donné en entrée du problème. Supposons pour l'exemple qu'il y en ait 6 :
Superman dispose d'un autre côté de plusieurs pierres de kryptonite verte et d'antikryptonite orange (il en a autant qu'il veut). Il doit disposer une pierre dans chaque emplacement. Par exemple :
Mais il y a une contrainte supplémentaire : pour ne pas être affaibli par la kryptonite, il faut nécessairement que la configuration orange, vert, orange, vert, orange, formée de 5 pierres, soit présente quelque part dans l'agencement qu'il propose.
Par exemple, avec 6 emplacements, il n'y a que 4 façons de résoudre le problème :
Pour le nombre d'emplacements indiqué en entrée, combien de configurations différentes permettent à Superman de respecter ces contraintes ?
Exemple
Si le nombre d'emplacements est 7, alors il y a 11 façons différentes de disposer les pierres.