Yo

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Talete
Messaggi: 742
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Yo

Messaggio da Talete » 04 nov 2017, 20:31

In una gara di matematica, ci sono $6$ problemi e $300$ studenti partecipanti. Gli studenti sono molto bravi: ogni problema è risolto da almeno $180$ studenti. Dimostrare che esistono due studenti tali che ogni problema è stato risolto da almeno uno dei due.

Bonus: se il numero di problemi è $p$ e il numero di studenti partecipanti è $s$, qual è il minimo $n$ tale che se ogni problema è risolto da almeno $n$ studenti, esistono di sicuro due studenti tali che ogni problema è stato risolto da almeno uno dei due?
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Talete
Messaggi: 742
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Yo

Messaggio da Talete » 11 nov 2017, 21:01

A me la risposta del bonus viene tipo

\[ n > \frac{\sqrt p-1}{\sqrt p}\cdot s.\]

(Bello rispondersi da soli, eh?)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

TheRoS
Messaggi: 28
Iscritto il: 25 feb 2018, 13:05

Re: Yo

Messaggio da TheRoS » 18 mar 2018, 15:54

Allora provo il primo punto.
Considero una griglia 6x300, dove nelle colonne ci sono i sei problemi mentre nelle righe i 300 studenti. Quindi diciamo che se una casella viene marcata con una "X", lo studente che si trova sulla riga della "X" ha risolto il problema che si trova sulla colonna di quest'ultima. Per le ipotesi in ogni colonna devono quindi essere segnate almeno 180 caselle segnate.
La prima osservazione è che c'è uno studente che ha risolto almeno quattro problemi. La media dei problemi risolti da ciascuno studente viene infatti maggiore o uguale a 3,6. Analizziamo dunque i seguenti tre casi.
1) C'è uno studente che ha risolto tutti e sei i problemi. Questo caso è banale: basta infatti prendere un altro studente a caso per avere la tesi.
2) C'è uno studente che ha risolto esattamente 5 problemi. Ciò significa che nella sua riga sono segnate tutte le caselle eccetto una; ragionando per assurdo tale studente non formerebbe una coppia che porterebbe alla tesi solo se la colonna che presenta la casella non segnata della sua riga non avesse alcuna casella segnata. Ciò è chiaramente assurdo perché tale colonna ne deve possedere almeno 180 segnate!
3) C'è uno studente che ha risolto esattamente quattro problemi. Ciò significa che la sua riga ha esattamente quattro caselle segnate e due no. Se per assurdo questo studente non si legasse con un altro per formare una coppia che porterebbe alla tesi, allora le due colonne dove si trovano le due caselle non segnate dovrebbero avere le caselle segnate in modo tale che non ci fossero due caselle segnate (ciascuna appartenente ad una colonna) che si troverebbero sulla stessa riga. Anche questa affermazione è assurda perché in quelle due colonne ci sono almeno 180 caselle segnate per ciascuna casella e quindi si avranno per forza due caselle sulla stessa riga (il minimo valore per non avere questo è infatti 150).

Talete
Messaggi: 742
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Yo

Messaggio da Talete » 21 mar 2018, 20:13

Okay, la soluzione è corretta. Hai idee per il bonus?
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

TheRoS
Messaggi: 28
Iscritto il: 25 feb 2018, 13:05

Re: Yo

Messaggio da TheRoS » 26 mar 2018, 21:45

Allora, innanzitutto mi torna il tuo stesso risultato, però non so se il procedimento è giusto.
Il ragionamento è analogo a quello che ho usato per il caso numerico: tabella $p$x$s$. Siamo sicuri che c'è uno studente che ha risolto almeno $[\frac{n\cdot p}{s}]$. Ora, siccome i casi si facilitano mano a mano che lo studente ha risolto un numero di problemi maggiore, prendiamo in considerazione proprio questo caso.
Lo studente preso in considerazione ha sulla sua riga $p-[\frac{n\cdot p}{s}]$ spazi vuoti; in particolare noi vogliamo che sulle rispettive colonne degli spazi vuoti non ci siano allineamenti. Per massimizzare il numero di caselle ammissibili senza allineamenti possiamo immaginare che per ogni riga, le colonne delle $p-[\frac{n\cdot p}{s}]$ caselle abbiano esattamente $p-[\frac{n\cdot p}{s}]-1$ caselle segnate su ogni riga. Di conseguenza il numero di caselle segnate sarebbero $(p-[\frac{n\cdot p}{s}]-1)s$. In particolare vogliamo tale valore minore o uguale a $n\cdot (p-[\frac{n\cdot p}{s}])$ (che sarebbe il minimo valore di caselle segnate secondo l'ipotesi che ci devono essere almeno $n$ caselle segnate per ogni colonna) in modo tale da avere allineamenti e perciò la tesi. Adesso calcoli.
\begin{align}
(p-[\frac{n\cdot p}{s}]-1)s\leq n\cdot (p-[\frac{n\cdot p}{s}])\\
(s-n)\cdot(p-[\frac{n\cdot p}{s}])-s\leq 0\\
\frac{p}{s}\cdot n^2-2np+(p-1)\cdot s< 0\\
\end{align}
E' facile notare che le soluzioni dell'equazione sono entrambe positive. La disequazione è valida per un bound di valori e quindi a noi interessa quello minore che sarebbe la soluzione minore dell'equazione:
\begin{align}
\frac{2p-\sqrt{4p^2-4p(p-1)}}{2p/s}=\frac{\sqrt{p}-1}{\sqrt{p}}\cdot s
\end{align}
Ora il problema è dimostrare che non esistano bound migliori.

Talete
Messaggi: 742
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Yo

Messaggio da Talete » 29 mar 2018, 11:09

Il procedimento mi pare corretto, il fatto che venga lo stesso risultato mio è una cosa parecchio positiva :)

Per mostrare che non esistono bound migliori forse basta dire che per $n$ troppo piccoli la disuguaglianza viene col verso opposto e quindi si riesce a trovare (per pigeonhole?) una configurazione brutta.

Comunque io l'ho fatto diversamente: consideriamo due studenti a caso. Qual è il valore atteso del numero di problemi che nessuno dei due risolve? Se questo valore atteso è minore di $1$, c'è una coppia in cui il numero di problemi che nessuno dei due risolve è $0$. La probabilità che un problema non sia risolto da uno studente è minore o uguale a $1-n/s$; la probabilità che non sia risolto nemmeno dal secondo studente è ancora $1-n/s$. Tutto questo va moltiplicato per $p$ e si deve sperare che sia minore di $1$:
\[\mathbb{E}\le \left(\frac{s-n}{s}\right)^2<\frac1p.\]
La soluzione per questo è proprio
\[n>\frac{\sqrt{p}-1}{\sqrt{p}}\cdot s,\]
come volevamo.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

UW54
Messaggi: 16
Iscritto il: 28 mar 2018, 16:15

Re: Yo

Messaggio da UW54 » 31 mar 2018, 20:51

Scusate ma perché con questa formula 151 non funziona se è palese che vada bene in questo caso?

Talete
Messaggi: 742
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Yo

Messaggio da Talete » 02 apr 2018, 13:30

UW54 ha scritto:
31 mar 2018, 20:51
Scusate ma perché con questa formula 151 non funziona se è palese che vada bene in questo caso?
Perché 151 dovrebbe essere palese scusa?
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

UW54
Messaggi: 16
Iscritto il: 28 mar 2018, 16:15

Re: Yo

Messaggio da UW54 » 02 apr 2018, 18:38

Per la dimostrazione fatta nel caso uno studente abbia risolto 4 problemi ce ne sarebbe almeno uno che ha risolto gli altri due perché mettere in una tabella di 300 righe per 2 colonne (prendiamo in considerazione solo questi due problemi) 180 X a colonna significa che almeno in una riga ci sono 2X.
Il ragionamento è analogo nel caso di 151 ed inoltre abbiamo la certezza che almeno uno studente abbia risolto almeno 4 problemi (la media di problemi risolti è 3,02)

Rispondi