Mathastrophique
Le plus ennuyeux, dans la mort, c’est de se dire qu’on part sans avoir résolu de grandes questions: dieu existe-t-il, la vitesse de la lumière peut-elle être dépassée, le PSG peut-il gagner le championnat de France, etc.. Dans mon cas personnel, il s’agit de certains problèmes de maths. Vous allez me prendre pour un fou, mais c’est la stricte vérité. Me dire que je quitterai ce monde sans avoir résolu certains exercices m’obsède. Et parmi tous ces problèmes non résolus, il en est un qui me taquine depuis près de 15 ans.
Heureusement, on parle, de nos jours, de crowdsourcing, de l’intelligence collective. En bref, on peut faire appel à l’intelligence de ses amis pour résoudre des problèmes qu’on n’arrive pas à résoudre soi-même. Alors je vous soumets cet exercice à la fois passionnant et maléfique.
Il s’agit d’un jeu, qui se joue avec des boules. Plus exactement 2xN boules, où N est un entier fixé. Ces boules sont numérotées: il y en a 2 qui portent le chiffre 1, 2 autres qui portent le chiffre 2, 2 autres qui portent le chiffre 3, et ainsi de suite jusqu’à N. En tout, 2xN.
Ensuite, on va disposer ces boules en file indienne, mais pas n’importe comment. On va faire en sorte qu’entre les 2 boules qui portent le chiffre k soient posées exactement k autres boules. Vous arrivez à visualiser le truc? Non? Bon, alors voici ce que cela donne pour N = 3 ou N = 4.
3 1 2 1 3 2
4 1 3 1 2 4 3 2
Simple, non? Alors voici l’énoncé en question:
Trouver toutes les valeurs de N pour lesquelles un tel arrangement est possible.
Et oui, cela ne fonctionne pas pour tout N. Prenez N = 5, par exemple, ou N = 6. Vous pourrez passer votre journée à les disposer dans tous les sens, c’est impossible. Idem pour N = 25 ou N = 26 (mais c’est nettement plus long à tester…)
Mais pour N = 12, il y a plusieurs solutions, comme celle-ci.
1 2 1 3 2 10 12 3 8 4 11 6 7 9 4 5 10 8 6 12 7 5 11 9
En fait, et c’est là où c’est obsédant, j’ai déjà réussi à montrer que si un tel arrangement existe, alors forcément N s’écrit sous la forme 4k ou 4k+3. C’est la réciproque que je peine à résoudre depuis 15 ans.
Vous me donnez un coup de main?
Hervé Kabla, ancien patron d’agence de comm’, consultant très digital et cofondateur de la série des livres expliqués à mon boss.
Crédits photo : Yann Gourvennec
Est-ce qu’on a le droit de connaitre la démonstration de l’implication ?
Bien sûr. On suppose qu’on a une solution pour 2*N boules.
Alors on note inf(i) et sup(i) les rangs des deux boules numérotées i, avec inf(i) < sup(i). Il y a k boules entre les 2 boules de rang k, ce qui s'écrit sup(k)-inf(k) = k + 1 La somme des écarts s'écrit alors: somme(sup(i)-inf(i)) = 2 + 3 + ... + N+1 = 1 + 2 + ... + N + N = N*(N+1)/2 + N = N*(3*N+1)/2 D'un autre côté, la somme des inf(i) et des sup(i) vaut: somme(inf(i)+sup(i)) = 1 + 2 + ... + 2*N = 2*N*(2*N+1)/2 = N*(4*N+2)/2 En retranchant ces deux égalités, on obtient: 2*somme(inf(i)) = N*(4*N+2 - 3*N-1)/2 = N*(N+1)/2 donc: somme(inf(i)) = N*(N+1)/4 Or somme(inf(i)) est un nombre entier, et de deux choses l'une: soit N soit N+1 est pair. Donc soit N = 4k, soit N+1=4k D'où l'implictaion... Qui montrera la réciproche?
Je ne suis pas loin d’avoir des préoccupations proche des tiennes, ou exprimé autrement, tu es la première personne que je vois exprimer ce genre de préoccupations que j’ai depuis l’age de 10 ans environ.
Si tu veux voir le bon côté des choses : à 20ans aurais tu pensé qu’on démontrerait ou infirmerait le théorème de fermat de ton vivant?
Est-ce que tu es allé par exemple sur des google groupes spécialisés comme fr.sci.maths ?
« Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver » – (Gaston Bachelard)
Je n’y avais pas pensé. J’avoue ne pas fréquenter souvent les groupes…
Le nombre de solutions augmente très rapidement :
3 : 1 solution (on ne compte pas les symétriques)
4 : 1 solutions
7 : 26 solutions
8 : 150 solutions
11 : 17 792 solutions
12 : 108 144 solutions
15 : plus de 8 millions (j’ai arrêté le calcul)
Il semblerait que trouver une solution ne soit pas un soucis, même si je conviens que cette remarque ne constitue pas une démonstration. Je voulais voir la tête des solutions, car il me semble difficile de faire une démonstration qui ne soit pas constructiviste (c’est-à-dire qui montre comment construire une solution).
Bref, la tête des solutions ne m’a pas trop aidé pour le moment.
D’accord pour le « constructivisme » nécessaire. Es-tu sur du résultat concernant le nombre de solutions? Pour 7, je n’en trouve que 9:
1 7 1 2 5 6 2 3 4 7 5 3 6 4
1 7 1 2 6 4 2 5 3 7 4 6 3 5
1 6 1 7 2 4 5 2 6 3 4 7 5 3
1 5 1 6 7 2 4 5 2 3 6 4 7 3
1 4 1 5 6 7 4 2 3 5 2 6 3 7
1 4 1 6 7 3 4 5 2 3 6 2 7 5
1 6 1 3 5 7 4 3 6 2 5 4 2 7
1 5 1 7 3 4 6 5 3 2 4 7 2 6
1 5 1 6 3 7 4 5 3 2 6 4 2 7
Je me souviens qu’au tout début, lorsqu’on m’avait posé ce problème (qui me l’avait posé, je ne le sais plus), j’avais réussi à montrer que si la relation est vraie pour N, alors elle est vraie pour 4N et 4N+3, en construisant la solution pour 4N ou 4N+3 à partir de celle à N. Je n’ai hélas pas réussi à retrouver cette construction.
Pour 7 j’ai ça :
7 3 6 2 5 3 2 4 7 6 5 1 4 1
7 2 6 3 2 4 5 3 7 6 4 1 5 1
7 3 1 6 1 3 4 5 7 2 6 4 2 5
7 2 4 6 2 3 5 4 7 3 6 1 5 1
7 1 4 1 6 3 5 4 7 3 2 6 5 2
7 1 3 1 6 4 3 5 7 2 4 6 2 5
7 2 4 5 2 6 3 4 7 5 3 1 6 1
7 4 1 5 1 6 4 3 7 5 2 3 6 2
1 7 1 2 5 6 2 3 4 7 5 3 6 4
5 7 1 4 1 6 5 3 4 7 2 3 6 2
5 7 2 3 6 2 5 3 4 7 1 6 1 4
5 7 4 1 6 1 5 4 3 7 2 6 3 2
1 7 1 2 6 4 2 5 3 7 4 6 3 5
2 7 4 2 3 5 6 4 3 7 1 5 1 6
5 7 2 6 3 2 5 4 3 7 6 1 4 1
3 7 4 6 3 2 5 4 2 7 6 1 5 1
3 6 7 1 3 1 4 5 6 2 7 4 2 5
2 6 7 2 1 5 1 4 6 3 7 5 4 3
4 1 7 1 6 4 2 5 3 2 7 6 3 5
2 3 7 2 6 3 5 1 4 1 7 6 5 4
5 1 7 1 6 2 5 4 2 3 7 6 4 3
6 2 7 4 2 3 5 6 4 3 7 1 5 1
5 2 7 3 2 6 5 3 4 1 7 1 6 4
3 5 7 2 3 6 2 5 4 1 7 1 6 4
3 5 7 4 3 6 2 5 4 2 7 1 6 1
2 4 7 2 3 6 4 5 3 1 7 1 6 5
Ca prouve que mon algo est foireux, et je viens de comprendre pourquoi, merci.