Forum de mathématiques - Bibm@th.net

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Comparaison de nombres réels

On considère un tableau carré de taille n, entier fini.

Chaque élément est repéré par la convention  standard :

[tex]a_{i,j}[/tex]

avec i = ligne et j=colonne.

On définit le nombre A tq :

[tex]A= \min_{\atop i}(\max_{\atop j} (a_{i,j}))[/tex]

et le nombre B tq :

[tex]B = \max_{\atop j}(\min_{\atop i} (a_{i,j}))[/tex]

Montrez qu'on a toujours l'inégalité suivante :

[tex]A \ge B[/tex]

Dernière modification par freddy (29-07-2009 16:10:13)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Comparaison de nombres réels

Salut,

Ton tableau contient donc n² nombres réels ?
Tous différents ?
Ces n² nombres sont choisis aléatoirement dans l'ensemble des réels sans limite supérieure ou inférieure ?

D'autre part, ta notation :
[tex]A= \min_{\atop i}(\max_{\atop j} (a_{i,j}))[/tex]
signifie bien que dans chaque ligne j, tu prends le plus grand nombre de ladite ligne puis le minimum A des n maximums ?

[tex]B = \max_{\atop j}(\min_{\atop i} (a_{i,j}))[/tex]

signifie bien que dans chaque colonne i, tu prends le plus petit nombre de ladite colonne puis le maximum B des n minimums ?

Et ta question est de montrer que, grosso modo, le plus petit des maximums est toujours supérieur ou égal au plus grand des minimums

Je pense que tu n'étais pas surpris du peu d'enthousiasme que rencontrait ton problème ?

@+

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : Comparaison de nombres réels

Hello yoshi,
en fait il s'agit d'un problème qui mélange bien formalisme et interprétation,
Pour y voir plus clair, il faut expanser , dans la formule A >= B, le premier opérateur (min pour A, max pour B)
sous forme de quantification universelle, (c'est ce que j'appelle la partie formelle).
Le reste suit alors en interprétant les choses à i et j fixés (ceux qui étaient quantifiés).

Et moi je trouve le problème rigolo : il permet au taupin ou à l'épicier de mieux comprendre ce qu'est un minimum ou un maximum, ... et de leur montrer que ces opérations là ne commutent pas !

++

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Comparaison de nombres réels

Re,

Le reste suit alors en interprétant les choses à i et j fixés (ceux qui étaient quantifiés).

Suit... de loin (très pour moi) ! Il y a un temps certain que je n'ai plus l'agilité de l'esprit du Taupin...
Comme souvent, ce type de déclaration me plonge dans un abîme de perplexité encore plus profond et comme la chaleur (que j'exècre) ralentit encore mon intellect, je vais laisser le soin à l'idée de me trouver...
Ce qui n'enlève rien au côté "rigolo" du pb ni à sa finesse.

Je ne réfléchirai pas de manière consciente, mais vais laisser du temps à la maturation pour se faire (éventuellement, parce que ce n'est pas mon type préféré d'exercices...)

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Comparaison de nombres réels

Salut,

Ton tableau contient donc n² nombres réels ? OUI

Tous différents ? pas nécessairement
Ces n² nombres sont choisis aléatoirement dans l'ensemble des réels sans limite supérieure ou inférieure ? OUI

D'autre part, ta notation :
[tex]A= \min_{\atop i}(\max_{\atop j} (a_{i,j}))[/tex]
signifie bien que dans chaque ligne i, tu prends le plus grand nombre de ladite ligne (OUI)  puis le minimum A des n maximums ? OUI

[tex]B = \max_{\atop j}(\min_{\atop i} (a_{i,j}))[/tex]

signifie bien que dans chaque colonne j, tu prends le plus petit nombre de ladite colonne puis le maximum B des n minimums ? OUI

Et ta question est de montrer que, grosso modo, le plus petit des maximums est toujours supérieur ou égal au plus grand des minimums OUI

Je pense que tu n'étais pas surpris du peu d'enthousiasme que rencontrait ton problème ? NON, pas trop.

@+

Ouaip, tu as bien résumé cette affaire.

Reste à le démontrer.

C'était une assez bonne introduction aux stratégies dite du minimax ou du maximin ... et aux fameux points cols des fonctions à deux variables.

En l'état, ce que je voulais était que les "prépas" s'appliquent à réfléchir juste. Pour les booster, je disais que chaque année, j'en avais au moins une qui trouvait et que ce serait dommage que la série s'arrête avec cette promo. Et que ce n'était pas nécessairement une "carrée" ...

Au passage, merci à Barbichu, notre maître à tous.

Bis bald

Dernière modification par freddy (02-08-2009 14:30:11)

kkloo

Invité

Re : Comparaison de nombres réels

hello,

Est-ce que le raisonnement à avoir ne serait pas:

Pour [tex]i=1,\ldots,n[/tex], on a

[tex]\max_j a_{ij} \geq \min_k a_{k1}[/tex]
[tex]\vdots[/tex]
[tex]\max_j a_{ij} \geq \min_k a_{kn}[/tex]

et donc

[tex]\max_j a_{ij} =M_i \geq \max_l \min_k a_{kl} = K[/tex]

Donc la suite [tex]M_i[/tex] est minorée par [tex]K[/tex].

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Comparaison de nombres réels

Salut,

Je crois que c'est faux.

Suggestion : utiliser un raisonnement par l'absurde ...

Have fun

kkloo

Invité

Re : Comparaison de nombres réels

Coucou,

Par l'absurde j'aboutis au même argument:  le max de toute ligne est  >=  au min de toute colonne (du fait que toute ligne a un élément en commun avec toute colonne).
Pourrais tu m'indiquer à partir d'où je raisonne faux? Je n'arrive pas à voir...

merci :)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Comparaison de nombres réels

hello,

Est-ce que le raisonnement à avoir ne serait pas:

Pour [tex]i=1,\ldots,n[/tex], on a

[tex]\max_j a_{i,j} \geq \min_k a_{k,1}[/tex]
[tex]\vdots[/tex]
[tex]\max_j a_{i,j} \geq \min_k a_{k,n}[/tex]

et donc

[tex]\max_j a_{i,j} =M_i \geq \max_l \min_k a_{k,l} = K[/tex]

Donc la suite [tex]M_i[/tex] est minorée par [tex]K[/tex].

Slt,

j'ai un peu modifié tes indices, pour les rendre plus lisible.

Quand tu écris :

Pour [tex]i=1,\ldots,n[/tex], on a

[tex]\max_j a_{i,j} \geq \min_k a_{k,1}[/tex]

je comprends que la valeur maximale du tableau carré est toujours supérieure à chaque valeur minimale de chaque ligne, ce qui est un truisme, non ?

Si tu voulais dire (ce qui est ce que tu dis en fait) :

Pour [tex]i=1,\ldots,n[/tex], on a

[tex]\max_j a_{i,j} \geq \min_k a_{k,i}[/tex]

t'es d'accord que rien ne le prouve.

Bis bald

kkloo

Invité

Re : Comparaison de nombres réels

La dernière inégalité que tu écris est vraie car
[tex]\min (a_{1,i},\ldots,a_{n,i}) \leq a_{i,i} \leq \max (a_{i,1},\ldots,a_{i,n})[/tex]
????

SInon j'avais découplé les indices i j k l car A et B ne dépendent pas de i ou j.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Comparaison de nombres réels

La dernière inégalité que tu écris est vraie car

[tex]\min (a_{1,i},\ldots,a_{n,i}) \leq a_{i,i} \leq \max (a_{i,1},\ldots,a_{i,n})[/tex]

...

Re,

ouais, ça, j'aime mieux, bcp mieux ! :-))

Et après, tu enchaînes comment ?

kkloo

Invité

Re : Comparaison de nombres réels

Pour la suite, c'est que j'avais écrit dans mon 1er post.

[tex]\min_k a_{k,1} \leq a_{i,1} \leq M_i[/tex]
[tex]\vdots[/tex]
[tex]\min_k a_{k,n} \leq a_{i,n} \leq M_i[/tex]

Donc la suite finie  [tex]M_i =  \max_j a_{i,j}[/tex] est minorée par le max-min.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Comparaison de nombres réels

Salut,

mouais, un peu capillotracté dans la présentation du raisonnement, ce qui rend la lecture un poil pénible, mais j'achète.

Sinon, voici plus léger en reprenant ton bon départ :

pour tout i et tout j, chacun élément du segment entier  [1 , n], on a :

[tex]m_j = \min_i (a_{i,j}) \leq a_{i,j} \leq \max_j (a_{i,j})=M_i[/tex]

Puisque cette inégalité est vraie pour tout  (i, j) élément  [1 , n]x[1 , n], elle est en particulier vraie pour le couple ( i*,j*) tel que :

[tex]m_j \leq m_j* \leq M_i* \leq M_i[/tex]

QED

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Comparaison de nombres réels

Re,

Bien entendu, on ne confondra pas les max(min) et les min(max), sauf cas d'espèce.

Plus précisément

[tex]B = m_j* = a_{i_j*,j*}[/tex]

et

[tex]A = M_i* = a_{i*,j_i*}[/tex]

et il n'y a aucune raison a priori que A = B.

Exemple  :

[tex]\begin{bmatrix} 4 & 6 & 2 \\ 7 & 5 & 9 \\ 8 & 3 & 1\end{bmatrix}[/tex]

On a

A = min(6, 9, 8) = 6 et B = max(4, 3, 1) = 4