Pagina 1 di 1

Yo

Inviato: 04 nov 2017, 20:31
da Talete
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?

Re: Yo

Inviato: 11 nov 2017, 21:01
da Talete
A me la risposta del bonus viene tipo

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

(Bello rispondersi da soli, eh?)

Re: Yo

Inviato: 18 mar 2018, 15:54
da TheRoS
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).

Re: Yo

Inviato: 21 mar 2018, 20:13
da Talete
Okay, la soluzione è corretta. Hai idee per il bonus?

Re: Yo

Inviato: 26 mar 2018, 21:45
da TheRoS
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.

Re: Yo

Inviato: 29 mar 2018, 11:09
da Talete
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.

Re: Yo

Inviato: 31 mar 2018, 20:51
da UW54
Scusate ma perché con questa formula 151 non funziona se è palese che vada bene in questo caso?

Re: Yo

Inviato: 02 apr 2018, 13:30
da Talete
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?

Re: Yo

Inviato: 02 apr 2018, 18:38
da UW54
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)