Côtés entiers

[acoustica]

Bonjour: un petit exo sympa mais pour lequel je n'ai pas de solution à proposer. J'espère que quelqu'un va en trouver une...

Soit un rectangle du plan divisé en petits rectangles. On suppose que chacun de ces petits rectangles admet un côté entier. Démontrer que le grand rectangle admet un côté entier.

:we:

[Doraki]

On me l'avait posé y'a longtemps j'avais fait une ébauche de démo mais a fortiori je suis pas sur que celle que j'avais aboutisse simplement.
Et puis la démo qu'on m'avait donnée était pas très... satisfaisante.

Maintenant j'ai une démo élémentaire que si le grand rectangle n'a aucun coté entier alors il existe un petit rectangle qui n'a aucun coté entier.

[ffpower]

et bien je connais une solution,courte mais pas tres satisfaisante:on suppose les cotés du rectangle paralleles aux axes.Soit L integrale de f sur chaque petit rectangle est nulle donc l integralde f sur le grand rectangle est nulle donc le grand rectangle a au moins un coté entier.

Cela dit on voit mal ce qui se passe avec cette methode.Par ex,changeons l enoncé ainsi:
Soit G un sous groupe de (R,+) (un ensemble stable par addition suffit peut etre).On suppose que chaque petit rectangle a au moins un coté dans G,montrer que le grand rectangle a au moins un coté dans G.

L exercice est probablement encore vrai dans ce cadre,mais la solution précédente ne marche pas ici..

[acoustica]

Maintenant j'ai une démo élémentaire que si le grand rectangle n'a aucun coté entier alors il existe un petit rectangle qui n'a aucun coté entier.

Oui, c'est sûr que il n'y a que deux façons de procéder. Le sens de l'énoncé ou la contraposée...poste ta démo! :we:

[acoustica]

et bien je connais une solution,courte mais pas tres satisfaisante:on suppose les cotés du rectangle paralleles aux axes.Soit L integrale de f sur chaque petit rectangle est nulle donc l integralde f sur le grand rectangle est nulle donc le grand rectangle a au moins un coté entier.

Cela dit on voit mal ce qui se passe avec cette methode.Par ex,changeons l enoncé ainsi:
Soit G un sous groupe de (R,+) (un ensemble stable par addition suffit peut etre).On suppose que chaque petit rectangle a au moins un coté dans G,montrer que le grand rectangle a au moins un coté dans G.

L exercice est probablement encore vrai dans ce cadre,mais la solution précédente ne marche pas ici..

On va essayer de faire avec des outils de lycée, dak?
Je ne comprend pas du tout ta démo, tu m'expliques?

[ffpower]

et bien,si on regarde un rectangle R=[a,b]x[c,d],l integrale de f sur R vaut
.En particulier cette integrale est nulle si et seulement si b-a ou d-c est entier,cad si et seulement si R a un coté entier.Par hypothese,on a donc que l integrale de f sur chque petit rectangle est nulle,donc en déduit que l integrale de f sur le grand rectangle est nulle...

[Doraki]

oui ffpower c'est la démo qu'on m'avait montré.
(mais c'est de la triche !!)

Voilà la version élémentaire de la preuve après un peu de travail :

On met un repère dans un coin du grand rectangle.
Je suppose que tous les petits rectangles ont leurs cotés parallèles à ceux du grand rectangle. (j'crois que t'as omis de le dire).

On suppose que le rectangle a ses 2 cotés non entiers.
Les cotés du rectangle sont donc (n+r1) et (m+r2) avec 0 < r1, r2 < 1.
Je choisis un nombre ex dans ]0; 1/2[, tel que r1-1/2 < ex < r1,
et un nombre ey dans ]0; 1/2[ tel que r2-1/2 < ey < r2, et puis aussi tels que ex et ey soient différent modulo 1/2 de toutes les coordonnées des cotés des petits rectangles (pour éviter des embrouilles)

Je regarde l'ensemble E des points de coordonnées (x/2 + ex , y/2 + ey) qui sont dans le grand rectangle pour x et y entiers.
Vu comme j'ai choisis ex et ey, E est de taille (2*n+1)*(2*m+1), qui est impair.

Maintenant puisque le grand rectangle est la réunion des petits rectangles, il y a au moins 1 petit rectangle contenant un nombre impair de points de E.
Or un rectangle de largeur ou de hauteur entière contiendra toujours un nombre pair de points de E.
Donc j'ai un petit rectangle dont les cotés ne sont pas entiers.

[Imod]

Je connaissais la démo de ffpower , il paraît qu'il y en a plein d'autres !

Imod

Edit :

Fourteen Proofs of a Result about Tiling a Rectangle
S. Wagon, American Mathematical Monthly, Vol. 94, (1987).

Il y en a eu sans doute d’autres depuis.

[acoustica]

"l integrale de f sur R vaut
"
Elle sort d'où cette intégrale (c'est surtout que je ne vois vraiment pas ce que l'exponentielle vient faire là-dedans)? :doh:

[acoustica]

Fourteen Proofs of a Result about Tiling a Rectangle
S. Wagon, American Mathematical Monthly, Vol. 94, (1987).

Il y en a eu sans doute d’autres depuis.

Bon bah puisque c'est la journée pour faire le plein de docs, si tu l'as en numérique... :ptdr: :ptdr:

[acoustica]

oui ffpower c'est la démo qu'on m'avait montré.
(mais c'est de la triche !!)

Voilà la version élémentaire de la preuve après un peu de travail :

On met un repère dans un coin du grand rectangle.
Je suppose que tous les petits rectangles ont leurs cotés parallèles à ceux du grand rectangle. (j'crois que t'as omis de le dire).

On suppose que le rectangle a ses 2 cotés non entiers.
Les cotés du rectangle sont donc (n+r1) et (m+r2) avec 0 < r1, r2 < 1.
Je choisis un nombre ex dans ]0; 1/2[, tel que r1-1/2 < ex < r1,
et un nombre ey dans ]0; 1/2[ tel que r2-1/2 < ey < r2, et puis aussi tels que ex et ey soient différent modulo 1/2 de toutes les coordonnées des cotés des petits rectangles (pour éviter des embrouilles)

Je regarde l'ensemble E des points de coordonnées (x/2 + ex , y/2 + ey) qui sont dans le grand rectangle pour x et y entiers.
Vu comme j'ai choisis ex et ey, E est de taille (2*n+1)*(2*m+1), qui est impair.

Maintenant puisque le grand rectangle est la réunion des petits rectangles, il y a au moins 1 petit rectangle contenant un nombre impair de points de E.
Or un rectangle de largeur ou de hauteur entière contiendra toujours un nombre pair de points de E.
Donc j'ai un petit rectangle dont les cotés ne sont pas entiers.

Ah oui, j'aime bien ces démos là!!
Vraiment joli... :happy2:

[ffpower]

"l integrale de f sur R vaut
"
Elle sort d'où cette intégrale? :doh:

Et bien la je n ai rien écrit.On veut calculer l integrale de f sur R sachant que et R=[a,b]x[c,d].Cette integrale vaut donc

[Imod]

Or un rectangle de largeur ou de hauteur entière contiendra toujours un nombre pair de points de E.
Donc j'ai un petit rectangle dont les cotés ne sont pas entiers.

Tu peux détailler s'il te plait ?

Imod

[Doraki]

Si le petit rectangle a par exemple sa largeur entière,

pour chaque point de E dans ce rectangle, si je regarde la ligne horizontale qui passe par ce point, la portion qui est dans le rectangle est donc un segment horizontal de longueur entière, avec un point de E placé tous les 1/2.

il ne peut y en avoir qu'un nombre pair sur ce segment. (si y'en avait un nombre impair 2k+1, la longueur du segment serait du style 2k*(1/2)+t1+t2 avec 0 < t1,t2 < 1/2, et ça pourrait pas être un entier).

Donc en classant les points de E selon les lignes horizontales sur lesquelles ils se trouvent, ils sont bien au total en nombre pair.


Sinon je vois dans le papier auquel tu réfères qu'il y a d'autres preuves pas équivalentes à celle-ci.

[Imod]

Et pourquoi r1 et r2 seraient-ils supérieurs à 1/2 ?

Imod

[Doraki]

bah justement ils le sont pas.
t1 et t2 sont les distances entre les extrémités du segment et les points de E les plus à gauche / à droite sur le segment.
On a pris E de manière à ce qu'il n'y ait aucun point sur la frontière d'un rectangle, donc t1, t2 > 0.
Il y a des points de E répartis tous les 1/2 sur cette ligne. comme on regarde les points les plus à gauche/à droite, on en déduit que t1, t2 < 1/2.

Si il y a un nombre impair de points de E sur ce segment,
la distance entre les 2 points extrêmes est (1/2)*2k donc un entier k,
et 0 < t1+t2 < 1, donc si on a un nombre impair de points de E sur la ligne, la largeur du rectangle, k+t1+t2, ne peut pas être entière.

[Imod]

J'avoue être un peu perdu avec tes notations , tu as écrit "ex dans ]0;1/2[ avec r1-1/2
Imod

[nodgim]

J'ai rarement vu un problème d'olympiade aussi simple.

Je progresse dans le grand rectangle de bas en haut. J'emprunte un rectangle entier vertical (EV). A son sommet, je progresse en suivant un autre EV, d'origine ou en cours, ça n'a pas d'importance. S'il n'y en a pas, c'est que je n'ai que des EH, donc la largeur du grand rectangle est entière. Sinon, je poursuis jusqu'en haut.

[Doraki]

Euh c'était pas les mêmes r1 et r2. que ceux du début.
En plus me suis embrouillé un peu dans les noms, donc bon j'ai renommé tout ça.

Nodgim, admettons qu'on colorie les rectangle de hauteur entière en rouge, et les rectangles de largeur entière en bleu.

Je suis (à peu près) d'accord qu'on peut trouver un chemin bleu de gauche à droite ou bien un chemin rouge de bas en haut, mais ça n'implique pas que tu obtiennes un chemin avec des rectangles tous bien positionnés.
Un chemin rouge peut emprunter des rectangles rouges dont l'ordonnée n'est pas entière.
Tu peux trouver un chemin rouge alors que c'était en fait la largeur du rectangle qui est entière.

[Imod]

Euh c'était pas les mêmes r1 et r2. que ceux du début.
En plus me suis embrouillé un peu dans les noms, donc bon j'ai renommé tout ça.

D'accord , je regarderai plus en détail tout à l'heure :we: mais dès ton premier message tu supposes que r1 et r2 sont supérieurs à 1/2 ( pour choisir ex et ey ) , il y a une raison ?

Imod