quesito di logica su una matrice

[laura123]

Si consideri la seguente matrice:
$
((a,b),(c,d))
$
Siano $k_1=max\{a,c\}$, $k_2=max\{b,d\}$, $t_1=min\{a,b\}$ e $t_2=min\{c,d\}$.
Che relazione c'è tra $max\{t_1,t_2\}$ e $min\{k_1,k_2\}$?

[Demostene92]

$max{t_1, t_2}=min{k_1, k_2}$.

[j18eos]

Come lo dimostri?

Possibilmente metti la tua soluzione in spoiler.

[laura123]

Quando ho proposto l'esercizio avevo ragionato così:

Testo nascosto, fai click qui per vederlo

Dalle definizioni si ha
$t_1<=a \mbox{ e } t_1<=b$
$t_2<=c \mbox{ e } t_2<=d$
$k_1>=a \mbox{ e } k_1>=c$
$k_2>=b \mbox{ e } k_2>=d$
Combinandole opportunamente seguono:
$t_1<=a<=k_1\ \ \ (1)$
$t_1<=b<=k_2\ \ \ (2)$
$t_2<=c<=k_1\ \ \ (3)$
$t_2<=d<=k_2\ \ \ (4)$

quindi da (1) e (3) segue $max\{t_1,t_2\}<=k_1$
da (2) e (4) segue $max\{t_1,t_2\}<=k_2$
allora $max\{t_1,t_2\}<=min\{k_1,k_2\}\ \ \ (5)$.

da (1) e (2) segue $min\{k_1,k_2\}>=t_1$
da (3) e (4) segue $min\{k_1,k_2\}>=t_2$
allora $min\{k_1,k_2\}>=max{t_1,t_2}\ \ \ (6)$

dalla (5) e dalla (6) segue $min\{k_1,k_2\}=max{t_1,t_2}$

Cosa ne pensate?

[Cmax]

Il quesito presenta una relazione con un problema presentato in televisione molti anni fa, a detta del conduttore proposto alle olimpiadi di matematica in URSS, prima che questo genere di competizione arrivasse anche in Italia.
Lo riferisco così come lo ricordo.

Un reparto di soldati, il cui numero non è precisato, viene disposto in uno schieramento quadrato, senza che rimangano posizioni vuote. Per ciascuna riga viene fatto uscire il soldato più basso e tra questi viene poi scelto il più alto. I soldati riprendono la loro posizione precedente. Da ciascuna colonna si sceglie poi il più alto, e di questi si sceglie il più basso. Può darsi che i due soldati così selezionati siano la stessa persona: si supponga che ciò non accada. È più alto il più alto dei più bassi o il più basso dei più alti?

Mi sembra che il conduttore riferisse, ma qui il ricordo è veramente labile, che era stato proposto per la categoria 14 anni nel 1974 o giù di lì.

PS. Trovato il problema (era leggermente diverso da come lo ricordavo o da come era stato riferito. È il 15.2.9.5, p.41 di questa raccolta. Si trattava delle Olimpiadi del 1952, ed i soldati non sono disposti in quadrato (termine usato nel suo significato militare, diverso da quello geometrico).

Testo nascosto, fai click qui per vederlo

Una soluzione credo si possa abbozzare in questo modo. Se $(i,j)$ è il più alto dei più bassi, e $(I,J)$, il più basso dei più alti, consideriamo il soldato $(i,J)$. Poiché $(I,J)$ è il più alto della sua colonna, allora $(I,J)>(i,J)$. Tuttavia $(i,j)$ è il più basso della sua riga, quindi $(i,j)<(i,J)$.

[j18eos]

@Laura123 A me torna tutto.

@Cmax Ma così non imiti il ragionamento di Laura?

[Cmax]

@Cmax Ma così non imiti il ragionamento di Laura?

Così come il problema è una versione differente dello stesso problema, la risoluzione non è un'imitazione, ma è la stessa, formulata in modo diverso. L'interesse che vi vedevo è storico: non vorrei che la memoria mi tradisse, ma la trasmissione in cui il problema veniva proposto era L'almanacco del giorno dopo, e non mi ero mai preoccupato di andare a ricercarne le fonti.

[Cmax]

Riesumo questo post per evidenziare uno degli esercizi assegnati questo a.a. per l'ammissione SNS I anno.

Siano $I$,$J$ insiemi non vuoti con un numero finito di elementi e sia $P : I \times J \rightarrow [0, 1]$ una funzione. Si considerino le due quantità

$L= \max_{i \in I} \min_{j \in J} P(i,j)$ (i.e. $L=\max_{i \in I} m_i$, con $m_i = \min_{j \in J} P(i,j)$)
$L' = \min_{j \in J} \max_{i \in I} P(i,j)$ (i.e. $L'=\min_{j \in J} M_j$, con $M_j = \max_{i \in I} P(i,j)$).
Una di queste quantità è sempre maggiore o uguale dell’altra. Quale? Si giustifichi con una dimostrazione la risposta, dando inoltre un esempio che mostra come la disuguaglianza possa essere stretta.

Purtroppo il link quotato sopra non è più attivo, ma sono sempre i soldati di sessanta anni fa ...

[coleridge]

@Laura123: La (5) e la (6) sono equivalenti.

[Cmax]

Via, se proprio ci si vuole ricondurre al gioco originario, provate con la matrice
\[ \left( \begin{array}{ccc}
1 & 2 \\
3 & 0 \end{array} \right)\]