Bonjour
ou si on pense que on a la solution qui tue ?

je pense que

 Cliquez pour afficher

soit dans tous les cas
n(n+1)/2

J'avais la même idée en tête mais comment justifier qu'on ne peut pas faire mieux ?

Imod

j'ai essayé  5x5:
Plusieurs solutions,mais il faut laisser 10 cases sans diagonale  soit
15/25.
Pour 9x9
Je trouve 45 diagonales et 36 cases sans
nous avons donc   10/16  15/25  45/81
Cela ressemble à  60% ,je vais voir la réponse
de mathafou ...

c'est vrai qu'on peut déplacer et tourner certaines cases sans en changer le nombre...

En comptant les nœuds de la grille et le nombre de diagonales tracées , on voit qu'il y a n+1 nœuds qui ne sont l'extrémité d'aucune diagonale . Je ne sais pas si cette remarque présente un intérêt quelconque .

Imod

Bonsoir,

J'ai l'impression qu'on peut montrer par récurrence que la configuration de mathafou est optimale. Je présente l'idée mais rigueur.

Partons du cas n impair, depuis en bas à droite sur le dessin de mathafou. C'est ce que j'appelle le cas n=1. Puis pour n=2 on ajoute les 3 carrés adjacents à cette case etc... J'admets que de partir depuis en bas à droite n'est pas naturel mais je voulais démarrer depuis une figure existante.

Pour n=1. Le mieux c'est 1 diagonale. Là ça va .
Pour n=3. On ne touche pas la case n=1. On "voit" qu'on ne peut pas faire mieux qu'ajouter 5 cases sur les 8 disponibles, par exemple, en remplissant toute la rangée 3 et la colonne 3 (comme le propose mathafou) et donc en ne mettant rien dans les ligne et colonne 2. Vu que tous les noeuds "extérieurs" de la ligne/colonne 2 sont occupés, alors si on veut  mettre quelque chose dans une case appartenant à la ligne 2 ou colonne 2,  on est contraint d'en retirer au moins un de la ligne/colonne 3 (= de libérer un nœud) donc le total demeure inchangé). On a beau réitérer le processus, on est contraint de déshabiller Paul pour habiller Jacques car in fine les noeuds extérieurs de la ligne/colonne 2 sont toujours tous occupés.

En généralisant, on passe du cas 2n+1 (quel qu'il soit) à 2n+3 en n'ajoutant jamais plus que 4n+5 diagonales.

Le cas n pair se traite de la même façon en allant de 2 en 2.

Bonne soirée

Même si je suis sûr que la limite est atteinte , je ne crois pas trop à la récurrence . Pour quelle raison une position maximale n+2 serait  nécessairement construite à partir d'une position maximale n ?

Imod

Bonjour,

Je tente de reformuler mon idée car je me rends compte que je n'ai pas écrit clairement.

L'idée  que je veux transmettre est que si l'on sait maximiser le nombre de diagonales parmi ces 2 "bandes" (voir image jointe), quel que soit le carré de taille 2N+1 "englobé" par ces bandes alors la solution est maximale pour le carré de taille 2(N+1)+1. Et ensuite j'affirme que quel que soit le carré de taille 2N+1 que j'ai, alors je ne pourrais jamais faire mieux que d'ajouter 4N+5 diagonales pour le carré de taille 2(N+1)+1. Le 4N+5 se voit en mettant des diagonales sur toutes la bande extérieure et en constatant qu'il est impossible d'en ajouter une dans la bande inférieure  sans devoir en retirer une de la bande extérieure. Et même si on réitère le procédé plusieurs fois, on est toujours obligé d'en enlever (au moins) une sur la bande du dessus.

Donc si on note U[2N+1] le nombre de diagonales dans le carré de taille 2N+1 alors je dis que U[2N+3]U[2N+1]+4N+5

Et comme mathafou propose un cas d'égalité ...

Erreur dans l'image jointe...

Je crois que ça marche mais il a fallu que je reformule tout à l'envers pour comprendre ( sans doute mon côté gaucher ) . Pour un L d'épaisseur 2 et de côté n on ne peut pas tracer plus de 2n-1 diagonales et on peut le faire sans contact avec les côtés intérieurs du L . Maintenant s'il existait un carré de côté n+2 avec plus de (n+2)(n+3)/2 diagonales alors en enlevant un L à ce carré on obtiendrait un nouveau carré de côté n avec au moins  (n+2)(n+3)/2 -(2n-1)  diagonales mais ce nombre est supérieur à n(n+1)/2 .

Imod

Bonjour,

Bonsoir

Sylvieg, en effet, et je pense que tu y parviens en inversant le sens des diagonales de la figure de mathafou, en en ajoutant 2 sur les bords et en en retirant un seul sur le bord extérieur. Il y a donc un trou dans la raquette.

Donc il y a une dépendance un peu plus compliquée : le découplage n'est pas total entre le cas 2n+1 et le cas 2(n+1)+1 car si on inverse le sens des diagonales on doit tenir compte de ce que contient le carré "intérieur" aux bandes.


On peut s'y prendre autrement en considérant cette figure (pièce jointe) qui semble donner le max de mathafou, et un "vrai" découplage entre les cas pour faire la récurrence.
On traite le petit carré bleu 3x3, puis on passe par récurrence au carré 7x7 à l'étape suivante (puis au cas 11x11 etc ...). Donc au lieu de traiter les bandes que j'évoquais, on traite les bandes qui font "tout le tour". Et là il semblerait que pour des bandes de taille extérieures N, on ne puisse pas placer plus de 4N-6 diagonales (en tous cas si on veut meubler la bande interne on est obligé d'en retirer un sur la bande externe, et cela indépendamment du sens des diagonales (c'est un argument qui manquait dans mon message précédent). Si c'est correct, on règle le cas des carrés de taille 4n+3.

Les carrés de taille 4n+1 se traitent en parant d'un carré central de taille 2x2 (je n'ai pas regardé dans le détail mais ça a l'air de marcher). Je suppose que la même logique s'applique aux cas pairs (à étudier).

La figure que j'avais trouvée pour L avec n = 5 et 10 diagonales :

En effet Sylvieg , ce n'est donc pas aussi simple

Imod

Désolée de casser un peu l'ambiance.

Désolée pour quoi ? Le sujet est relancé
Imod

La proposition de Sylvieg  16 pour 25 ne valide plus la théorie à la mode...
On remarque 2x8 diagonales opposées  on présume donc que pour
7x7 on doit pouvoir placer 29 diagonales?

Soit en rajoutant 12 bleues:

Bonjour,

grâce à la figure donnée par Sylvieg on voit que le problème a déjà été étudié :

Oui et dans le cas d'un carré de côté pair la formule donnée par Mathafou est bonne et se démontre bêtement avec un coloriage des nœuds du quadrillage . Le cas impair est "un peu" plus complexe
Imod

@Dpi : ton intuition était bonne , pour n=7 on peut tracer 29 diagonales :


Imod

Pour n = 7 on peut utiliser un "L" comme décrit par thetapinch27.
En détail :
Dans la figure de dpi on peut mettre les 13 diagonales bleues au bord et identiques à celle qui est en haut à droite.
Et on peut continuer ensuite pour tous les n impairs.

Mais ça se casse la figure dès n = 11 où le maximum est 68 et pas 67.

Merci jandri pour ton lien. C'est là que j'ai trouvé , un PDF où il y a 68 pour n = 11.
On y voit aussi que la configuration est toujours la même pour n pair.

Oui , il suffit que les lignes 2 et 4 soient saturées , c'est la démonstration avec le coloriage .
Imod