Tableau de réels...

[Ben314]

Une toute petite énigme (mais vraiment toute petite)

On considère un tableau rectangulaire rempli de nombres réels tous différents.
On tri les éléments de la première ligne pour les mettre dans l'ordre croissant (de gauche à droite) puis ceux de la second ligne, puis ceux de la troisième ... etc jusqu'à la dernière ligne.
On tri maintenant les éléments de la première colonne pour les mettre dans l'ordre croissant (de haut en bas) puis ceux de la deuxième colonne, puis ceux de la troisième... jusqu'à la dernière colonne.

Les lignes sont elles encore dans l'ordre croissant aprés le tri des colonnes ?

[nodjim]

On représente, après le 1er tri, dans un repère 0xy les points d'une ligne du tableau et on trace une polyligne qui passe par tous ces points. On trace toutes les polylignes qui sont forcément toutes croissantes. Il me semble que le second tri ne fait que supprimer les croisements, ce qui répond à la question.

[Ben314]

On représente, après le 1er tri, dans un repère 0xy les points d'une ligne du tableau et on trace une polyligne qui passe par tous ces points. On trace toutes les polylignes qui sont forcément toutes croissantes. Il me semble que le second tri ne fait que supprimer les croisements, ce qui répond à la question.

Une preuve légèrement plus formelle qu'un "il me semble..." serait... fortement apréciée...

[ffpower]

( Le probleme revient à montrer que si on a 2 suites finies (u_n) et (v_n) telle que (u_n) minore (v_n) ( dans le sens u_n<v_n pour tout n) alors le "réordonnement croissant" de (u_n) minore le réordonnement croissant de (v_n). Quitte à faire un premier réordonnement commun, on peut supposer (v_n) croissante. Alors, supposons que (u_n) atteint son min en n=p. Trivialement, u_1 et u_p sont plus petits que tous les v_n ( u_p<u_1<v_1<v_n ), donc si dans la suite (u_n) on échange u_1 et u_p, la nouvelle suite obtenue minore encore (v_n). A partir de là on reccure aisément )

[Ben314]

FARFAITEMENT... :king2:

[Doraki]

Avec la fin qui change, et en remettant la généralité :


On trie une fois le tableau pour obtenir un tableau u_i^j avec u_i croissante pour tout i.
Le réordonnement donne un tableau v_i^j où v_i^j = le i-ème plus petit terme de la suite u^j.

Soit donc i quelconque et j<k.
v_i^j <= v_i^k car v_i^k est le ième plus petit terme de la suite u^k, chacun des i termes correspondants dans la suite u^j est encore plus petit donc u^j contient au moins i termes qui sont plus petits que v_i^k, et comme v_i^j est le i-ème plus petit terme de cette suite il est lui aussi plus petit que v_i^k

[Sve@r]

Une preuve légèrement plus formelle qu'un "il me semble..." serait... fortement apréciée...

Ok.

Bon, déjà on peut laisser tomber le tri des lignes et on admettra que les lignes sont déjà triées d'entrée. En effet, cette phase de tri préalable n'apporte rien d'autre que charger inutilement le problème.

Donc la question principale, c'est "si on trie les colonnes, est-ce que cela conserve le tri des lignes ?".

Prenons une matrice abcd avec ab et cd 2 lignes triées (a d. La matrice change et les lignes deviennent ad et cb. De plus, on sait que a Les lignes sont donc toujours triées
- a > c et b Les lignes sont donc toujours triées
- a > c et b > d. La matrice change et les lignes deviennent cd et ab mais chaque ligne reste identique et les lignes restent toujours triées.

Enfin quelle que soit la matrice initiale, on pourra toujours la décomposer en matrice 2x2 donc il me semble que cette démonstration suffit pour dire sans contestation qu'on conserve toujours des lignes triées après le tri des colonnes... :zen:

[nodjim]

Il est facile de trouver une preuve par le détail puis par récurrence. Nettement moins d'en trouver une par logique globale.