Petites enigmes > Réponse Sciences sujet

Pour le problème précédent : une stratégie simple : retourner la première moité des nombres, en noter le maximum M. Retourner ensuite des papiers de la deuxième moitié jusqu'à trouver une valeur dépassant M. S'arrêter alors. Cette stratégie garantit une probabilité > 1/4 de réussir.

On place une valise V1 (pavé droit ou parallélépipède rectangle) dans une valise V2. Montrer que la somme des trois dimensions de V1 est inférieure à la somme des trois dimensions de V2.

Donner un algorithme qui permet de trouver une paire de points les plus proches dans le plan et qui soit meilleur que quadratique (strictement).

Des balles numérotées entrent et sortent d'une boite. On veut écrire un programme qui permet de dire à chaque instant si toutes les balles dans la boite portent le même numéro. On dispose pour cela d'un nombre borné de cases mémoires, dont le contenu doit rester polynomial entre (N+M) (N étant le nombre total de boules rentrées, M le nombre de couleurs).
(La dernière précision est juste là pour éviter un codage rébarbatif du contenu de la boite).