gara matematica 2

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
quismulta
Messaggi: 29
Iscritto il: 01 gen 1970, 01:00

gara matematica 2

Messaggio da quismulta » 02 mag 2006, 23:48

Sulla falsariga di What ripropongo un problema abbastanza standard ormai (se ricordo bene l' avevo inviato anche nel vecchio forum) e proviene da una vecchia IMO.


21 ragazzi e 21 ragazze partecipano ad una gara matematica

ogni concorrente risolve al massimo 6 problemi
per ogni ragazza ed ogni ragazzo almeno un problema viene risolto da entrambi

si provi che c' era un problema che è risolto da almeno 3 ragazzi e almeno 3 ragazze




(Dato che ,se ricordo le statistiche, mi sembra che quasi tutti i concorrenti lo hanno saputo svolgere bene ,il quesito non è adatto agli "esperti".)
Ultima modifica di quismulta il 09 giu 2006, 23:56, modificato 1 volta in totale.

Araganaus
Messaggi: 2
Iscritto il: 08 mag 2006, 19:37

Messaggio da Araganaus » 08 mag 2006, 19:56

Allora... io non sono un "esperto"...
.. ma il problema mi sembra tanto semplice che la possibilità di starlo sbagliando mi sembra alta...

Dunque, se ci sono 21 coppie ragazzo-ragazza, ognuna delle quali risolve almeno un problema, nel caso più sfortunato effettivamente ogni coppia risolve un solo problema. Anche in questo caso, però, anche volendo distribuire nella maniera più uniforme possibile le soluzioni, possiamo "spargere" sui sei problemi 18 soluzioni, dando così ad ogni problema almeno tre coppie ragazzo-ragazza che risolvono il problema correttamente. Distribuendo poi in maniera non uniforme le soluzioni, certamente se ne avrebbe una che ne ha più di tre.
Ho detto una cavolata?
"Nulla è impossibile, basta decidere che tutto è possibile"

Araganaus

Ale the punisher
Messaggi: 15
Iscritto il: 07 mag 2006, 20:11
Località: Pisa

Messaggio da Ale the punisher » 11 mag 2006, 22:23

Uhm... non si dimostra col Principio dei cassetti? Cioè, se non ho capito male il testo (cosa probabile), bisogna dimostrare che di 6 problemi almeno uno viene risolto da almeno 3 ragazzi e 3 ragazze, quindi 3 coppie, dunque ponendo n=12 in questo caso perché 12 è il numero limite di spazi altrimenti dividendo per 6 si supera la quota e si arriva a tre coppie n+k=21 ovvero il numero di coppie a disposizione dimostriamo che il problema è risolto per il rpincipio dei cassetti perché dovendo disporre n+k oggetti in n cassetti almeno un cassetto conterrà più di un oggetto.
"Alea iacta est"

Membro del club dello sgabuzzino

MindFlyer

Re: gara matematica 2

Messaggio da MindFlyer » 12 mag 2006, 16:18

quismulta ha scritto:proviene da una vecchia IMO.
E' del 2001.
Grazie per il "vecchia", sigh. :cry:

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 09 giu 2006, 19:28

Ma forse sono solo io che non ho trovato la strada carina..però mi è parso un bel po' più difficile del problema di What :roll:

Vabbè ci provo..

Ad ogni problema assegno una coordinata (m,f) pari al numero di maschi e di femmine che hanno risolto quel problema.
Non considero i problemi risolti da soli maschi o da sole femmine in quanto cancellandoli ottengo una configurazione equivalente (in cui la tesi è vera sse era vera nella precedente e che è accettabile sse lo era la precedente).

Ipotizzo che:
1) Le coordinate m,f di ciascun problema siano >1
2) Esista un maschio (A) tale che tutte le coordinate m dei problemi da esso risolti siano>2
3) Nessun problema abbia coordinate (2,2)
4) Essendo n il numero di problemi risolti da almeno una persona sia 16>n

Step 1:
5)ipotizzo la tesi falsa.

Considero A.
Ognuna delle 21 ragazze ha risolto almeno un problema dei problemi risolti da A.
Se la tesi fosse falsa la coordinata f di ciascuno dei problemi risolti da A sarebbe 2.
Il numero di soluzioni dato dalle femmine ai problemi risolti da A sarebbe al massimo 6*2=12 ma ne servirebbero almeno 21, che è assurdo.

Step 2:
Se la 2 è falsa allora considerati i k problemi con coordinata m=2 necessariamente $ 2k \ge 21 $ (poiché tutti i 21 maschi hanno risolto almeno un problema con coordinata m=2;altrimenti esisterebbe un A con tale proprietà) ovvero $ k \ge 11 $ .
Inoltre se la tesi fosse falsa i problemi a coordinata F =2 sono $ j = n-k \ge n-11 $ ovvero considerando l’intervallo dei valori accettabili per n ottengo: $ j \leq 4 $.
Per cui necessariamente esisterebbe una ragazza B tale che tutte le coordinate f dei problemi da essa risolti siano $ \ge 3 $ (poichè $ 2*4 \leq 21 $).
Posso ora rieffettuare un ragionamento analogo al punto precedente.

Step 3:
Ipotizzo ora che n non appartenga all’intervallo considerato.

Ogni problema ha una coordinata m e una f; una coordinata è 2 mentre l’altra è $ k_i\ge 3 $ (posso supporre che le coordinate m,f non siano entrambe $ \ge 3 $ mentre per l’ipotesi 1 e 3 almeno una coordinata è maggiore di 2).
So che: il numero massimo di soluzioni è 252 = (6*42).
Quindi ho che:
$ 2n+ \sum_{i=1}^{n}k_i \leq 252 $

Inoltre ogni problema con coordinate (m,f)= (2,k_i) (o viceversa) fa in modo che ognuno dei 2 maschi abbia risolto un problema in comune con k_i ragazze (o viceversa fa in modo che ognuna delle 2 ragazze abbia risolto un problema in comune con k_i ragazzi).
Ognuno dei 21 ragazzi deve risolvere almeno un problema in comune con ciascuna ragazza quindi:
$ 2 \sum_{i=1}^{n}k_i > 21*21 $

da cui:
$ 252-2n \ge \sum_{i=1}^{n}k_i $ > $ \frac{21*21}{2} $ ovvero (considerando il primo e il terzo membro)
$ n \leq 15,75 $ che è assurdo; quindi appartiene all’intervallo considerato.

Step 4:
Ipotizzo che esistano dei problemi con coordinate (2,2).
Sia $ P_1 $ uno di questi problemi:
posso cancellare questo problema e creare una situazione corrispondente nella quale la verità/falsità della tesi rimanga invariata ma nella quale sia rispettata la condizione 3 come segue:

Considero un solutore di $ P_1 $ maschio $ M_1 $ .
Tra gli esercizi risolti da $ M_1 $esiste sicuramente $ P_2 $ uno con coordinata f>2.
Ho infatti che la somma delle coordinate f degli esercizi risolti da $ M_1 \ge 21 $ poiché $ M_1 $ ha risolto un’erercizio in comune con ciascuna ragazza.
La media delle coordinate f negli esercizi risolti da $ M_1 $ (senza considerare P_1) è $ \ge \frac{21-2}{6} >3 $ quindi esiste un problema con la proprietà richiesta.
Posso aggiungere questo esercizio agli esercizi risolti da una (F_1) delle due solutrici di $ P_1 $ (se essa non ha già risolto $ P_2 $ ovviamente) .
Analogamente tra gli esercizi risolti da F_2 ne posso scegliere uno tale che abbia coordinata m>2.
Posso aggiungere questo esercizio agli esercizi risolti da $ M_1 $ (se esso non l’ha già risolto) .
Procedo analogamente con il secondo solutore di $ P_1 (M_2) $ (invertendo $ F_1 $ e $ F_2 $).
Così facendo: modifico solo coordinate f,m>2; lascio inoltre che ogni coppia (maschio;femmina) formata tra $ F_{1,2} $ e $ M_{1,2} $ abbia ancora almeno un problema risolto in comune.
Inoltre se il numero di problemi risolti da $ M_i $ o $ F_i $ era minore di 7 lo sarà ancora. E’ inoltre palese che questa mossa non aumenta i problemi a coordinata (1,k)o (k,1).
Noto che sse la prima configurazione era accettabile lo sarà anche la seconda.
Noto che sse la tesi era vera nella prima configurazione lo sarà anche in questa.

Step 5:
Ipotizzo ora che esita almeno un problema $ P_3 $ con almeno una coordinata pari ad 1 (wlog le coordinate di $ P_3 $ sono (1,k) con $ k \ge 1 $).
Posso cancellare questo problema e creare una situazione corrispondente nella quale la verità/falsità della tesi rimanga invariata ma nella quale sia rispettata la condizione 1 come segue:
Sia $ M_3 $ l’unico solutore maschio di questo problema.
Tra gli esercizi risolti da $ M_3 $ne esiste almeno ($ P_4 $) uno con coordinata f>2 (come ribadito sopra).

Se questo esercizio non è $ P_3 $ (se esiste almeno un’esercizio risolto da M_3 diverso da $ P_3 $ con questa proprietà) allora proseguo come segue.

Posso quindi aggiungere questo esercizio agli esercizi risolti dalle k solutrici di $ P_3 $ (se esse non hanno già risolto $ P_4 $ ovviamente) .
Ovviamente nulla mi assicura che $ P_4 $ non abbia coordinata m=1.
Procedo analogamente se incontro eventuali altre coordinate 1, infatti questa mossa, quando la posso applicare fa calare strettamente il numero di problemi a coordinata 1 fino ad arrivare ad una situazione in cui non è più applicabile (caso che tratterò in seguito) oppure ad una situazione in cui non ho problemi a coordinata 1. E’ inoltre palese che questa mossa non aumenta i problemi a coordinata (2,2).
Noto che sse la prima configurazione era accettabile lo sarà anche la seconda.
Noto che sse la tesi era vera nella prima configurazione lo sarà anche in questa.

Non resta che analizzare i casi nei quali la strategia dello step 5 non è applicabile.
Ultima modifica di enomis_costa88 il 09 giu 2006, 22:21, modificato 1 volta in totale.
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 09 giu 2006, 19:29

Step 6:
Se non è applicabile vuole dire che tra gli esercizi risolti da $ M_3 $ l’unico con coordinata $ f\ge 3 $ è $ P_3 $.
Inoltre la somma delle coordinate f dei problemi risolti da $ M_3 $ è almeno 21 (poiché $ M_3 $ deve avere risolto un problema in comune con tutte le 21 ragazze) e la chiamo Z.
Ottengo (poiché nessun’altro problema risolto da $ M_3 $ può avere coordinata f>2) che $ 2*5+k\ge Z \ge 21 $ da cui $ k\ge 11 $.
Quindi posso facilmente ricondurmi ad una situazione in cui ogni maschio abbia risolto al più un problema del tipo (1,k) con $ k \ge 11 $ e ogni femmina al più uno del tipo (k,1) con $ k \ge 11 $
Altrimenti potrei applicare la strategia dello step 5 poiché avrei che o tutti i problemi del tipo (1,k) hanno $ k\leq 2 $ e quindi esiste un altro $ P_i $ con coordinata $ f \ge 3 $, oppure avrei almeno un problema del tipo (1,k) con $ k \ge 3 $ e posso applicare la strategia dello step 5 trattando questo problema come$ P_4 $.
In questo modo applico una discesa sul numero di problemi del tipo (1,k); non posso più applicare questa discesa quando rimango con un solo problema con k>10.

Step 7:
Considero ora tra gli esercizi risolti da un maschio generico $ M_4 $ il numero di esercizi $ P_i $ del tipo (k,1) con $ k\ge11 $ (poiché altrimenti esisterebbe una ragazza che ha risolto $ P_i $ del tipo (k,1) con $ k\leq 10 $ e quindi potrei riapplicare la strategia dello step 5).
Ipotizzo siano più di uno $ (P_5,P_6,..,P_j) $ le cui solutrici siano $ (F_5,..,F_j) $.
In questo caso posso cancellare $ P_5 $e aggiungere $ P_6 $ agli esercizi risolti da $ F_5 $.
Aggiungo inoltre $ P_6 $ agli esercizi svolti da ciascun maschio che aveva risolto $ P_5 $ ma non $ P_6 $.
In questo modo $ F_5 $ ha ancora risolto un problema in comune con tutti i maschi che avevano risolto $ P_5 $.
Inoltre gli esercizi da essa svoti non aumentano come non aumentano gli esercizi svolti dai maschi che avevano risolto $ P_5 $.
$ P_5 $ viene cancellato e $ P_6 $diviene del tipo (k,2) con $ k \ge 11 $ . in questo modo posso fare calare di due in due il numero di esercizi del tipo (k,1) risolti da $ M_4 $ finchè $ M_4 $ non ne abbia risolti al più uno.
Noto quindi che sse la prima configurazione era accettabile lo sarà anche la seconda.
Noto che sse la tesi era vera nella prima configurazione lo sarà anche in questa.
Ultima modifica di enomis_costa88 il 09 giu 2006, 21:06, modificato 2 volte in totale.
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 09 giu 2006, 20:00

Step 8:
Ipotizzo ora che $ M_5 $ abbia risolto sia un esercizio $ P_7 $del tipo $ (1,k_7) $ che un’esercizio $ P_8 $ del tipo $ (k_8,1) $.
Palesemente risulta $ k_7\ge12 $ poiché $ 2*4+1+k_7\ge S \ge 21 $.
Posso quindi prendere una femmina $ F_7 $ solutrice di $ P_7 $ e “spostarla” su $ P_8 $ (ovvero questa ragazza non ha più risolto $ P_7 $ ma $ P_8 $) in questo modo essa ha ancora risolto un problema in comune con $ M_5 $ e il numero di problemi da essa risolto non aumenta.
Noto quindi che sse la prima configurazione era accettabile lo sarà anche la seconda.
Noto che sse la tesi era vera nella prima configurazione lo sarà anche in questa.

Step 9:
Posso quindi ricondurmi ad una situazione nella quale ogni solutore abbia al più un problema con una coordinata uguale ad uno.
In questo modo posso dimostrare che i problemi con una coordinata pari ad uno sono al massimo 3.
Infatti dato un problema (1,k) ottengo che nessuna delle k femmine ne il maschio hanno risolto altri problemi con una coordinata pari ad uno. Inoltre $ 1+k\ge 12 $.
Quindi per ogni problema (1,k) (un ragionamento analogo vale per (k,1) 12 persone non ne hanno risolto altri del tipo (1,k) o (k,1).
Il numero massimo di tali problemi sarà quindi $ [\frac{21+21}{12}]=3 $.

Step 10:
Siamo $ k_m $ e $ k_f $ il numero di coordinate m e f pari ad uno.
Siamo $ j_m $ e $ j_f $il numero di coordinate m e f pari a due.
Per quanto detto $ k_m+k_f\leq 3 $

Ottengo $ k_m+2j_m\ge 21 $ e analogamente
$ k_f+2j_f \ge 21 $ altrimenti avrei un solutore maschio i cui problemi risolti abbiano tutti m >2 oppure una solutrice i cui problemi risolti abbiano tutti f>2 e posso applicare un ragionamento analogo a quello dello step 1 raggiungendo un’assurdo.

Dalle due disuguaglianze precedenti ottengo:
$ k_m+k_f+2(j_m+j_f)\ge 42 $.
$ 3+j_m+j_f\ge n= k_m+k_f+j_m+j_f \ge 42-j_m-j_f $
ovvero: $ j_m+j_f\ge 20 $.
Palesemente $ n\ge 20 $.

Sia $ A=j_m+j_f $
Sia $ S=n-A=k_m+k_f $.
Siano chiamate $ j_i $ le coordinate non 2 dei problemi del tipo (2,j_i) e (j_i,2).
Siano chiamate $ k_i $ le coordinate non 1 dei problemi del tipo (1,k_i) e (k_i,1).

Poichè ognuno dei 21 ragazzi deve risolvere almeno un problema in comune con ciascuna ragazza ottengo:
$ 2\sum_{i=1}^{A}j_i+\sum_{i=1}^{S}k_i\ge 21*21 $

inoltre:
$ 2A+(n-A)+ \sum_{i=1}^{A}j_i+\sum_{i=1}^{S}k_i\leq 252 $
poiché il numero totale di soluzioni è al massimo 252.

Quindi facilmente:
$ 252-\sum_{i=1}^{S}k_i-A-n\ge $ $ \sum_{i=1}^{A}j_i\ge \frac{21*21- \sum_{i=1}^{S}k_i }{2} $
ovvero dopo pochi conti:
$ 2(252)-11S-21*21\ge 2(252)-21*21 $- $ \sum_{i=1}^{S}k_i\ge 2(A+n) $=2(2n-S)
ovvero:
$ n\leq\frac{2(252)-21*21-9S}{4} $ $ \leq 16 $
quindi $ n\leq16 $ ma anche $ n\ge 21 $ che è assurdo.
Ultima modifica di enomis_costa88 il 09 giu 2006, 20:50, modificato 1 volta in totale.
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

Hr 47
Messaggi: 15
Iscritto il: 12 mar 2006, 13:20
Località: Carrara

Messaggio da Hr 47 » 09 giu 2006, 20:28

O.T.: Se è sbagliata fate finta di niente, sennò si suicida.. :P Ci avrà messo tre giorni a scriverla.. :shock:

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 15 giu 2006, 10:11

enomis_costa88 ha scritto:Vabbè ci provo..
...ci provo anch'io...

Questi me li tengo per referenza:
enomis_costa88 ha scritto: 1) Le coordinate m,f di ciascun problema siano >1
2) Esista un maschio (A) tale che tutte le coordinate m dei problemi da esso risolti siano>2
3) Nessun problema abbia coordinate (2,2)
4) Essendo n il numero di problemi risolti da almeno una persona sia 16>n
Lo Step 1 dice: (1) + (2) + (3) + (4) ==> tesi. Ok, mi torna.

Lo Step 2 dice: Eventualmente scambiando il ruolo di maschi e femmine (tanto il problema è simmetrico), (1) + (3) + (4) ==> (2) [e quindi la tesi, per Step 1]. Anche questo mi torna.

Lo Step 3 dice: (1) + (3) ==> (4) [e quindi th.]. Ok anche qui, anche se ci sono dei minori stretti che dovrebbero essere minori uguali...

Lo Step 4 dice: non è restrittivo supporre che (3) sia vera. Qui inizio ad avere dei guai. in particolare:
Step 4:
[...](se essa non ha già risolto $ P_2 $ ovviamente).
Ovviamente. Ma chi ti garantisce che esista? Qui mi pare ci stia il passaggio chiave dello Step, quindi va compreso a fondo se torna oppure no. Prova a riscrivere questo pezzo di dimostrazione...

Gli steps da 5 in poi... al prossimo giro.

Nota stilistica: la matematica non è come i libri gialli, dove se si svela l'assassino prima dell'ultima pagina, lo scritto non vale un granché.

Quando si scrive una dimostrazione così lunga e articolata, è buona norma dire chiaramente dove si va a parare: hai fatto lo sforzo di dividere la soluzione in steps; sarebbe stato bene mettere un enunciato davanti a ciascuno di essi, senza che lo sventurato lettore dovesse fare anche lo sforzo supplementare di capire dove diavolo volessi arrivare.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 15 giu 2006, 18:29

Ho chiamato $ P_1 $ un esercizio con coordinate (2,2) questo esercizio ha 2 solutori $ (M_1,M_2) $ e 2 solutrici $ (F_1,F_2) $.
Tra gli esercizi risolti da $ M_1 $ ne esiste SICURAMENTE almeno uno con coordinata $ f\ge3 $, questo esercizio non può essere $ P_1 $ (infatti $ P_1 $ ha coordinata $ f=2 $) e lo chiamo $ P_2 $ .

Perché esiste sicuramente $ P_2 $ ?

Perché se non esistesse ciascun esercizio risolto da $ M_1 $ avrebbe coordinata f=1,2.
La somma delle coordinate f degli esercizi risolti da $ M_1 $ sarebbe al massimo 2*6=12.
Ma per ipotesi (ogni maschio ha risolto almeno un esercizio in comune con ciascuna ragazza) deve essere almeno 21 che è assurdo.
Quindi esiste sicuramente $ P_2 $ distinto da $ P_1 $.


Per quanto riguarda i passaggi (scusa :oops: mi ero dimenticato di scriverli..) :

Step 1: 1) + (2) + (3) + (4) ==> tesi.

Step 2: Eventualmente scambiando il ruolo di maschi e femmine (tanto il problema è simmetrico), (1) + (3) + (4) ==> (2)

Step 3: (1) + (3) ==> (4) (i minori vanno bene anche strettamente perché $ 21*21 \not=2 \sum_{i=1}^{n}k_i $ , un pari non è mai uguale ad un dispari..)

Step 4: non è restrittivo supporre che (3) sia vera.

Step 5: è restrittivo supporre (1) vera. Definisco una strategia utilizzabile in determinati casi per ridurre il numero di problemi del tipo (1,k) o (k,1).

Step 6: Non è limitativo supporre che ogni maschio abbia risolto al più un’esercizio con coordinata m=1.
Inoltre non è limitativo supporre che la coordinata f di questo esercizio sia >10
Analogamente non è limitativo supporre che ogni femmina abbia risolto al più un’esercizio con f=1
Inoltre non è limitativo supporre che la coordinata m di questo esercizio sia >10

Step 7: Non è limitativo supporre che ogni maschio abbia risolto al più un’esercizio con coordinata f=1.
Analogamente non è limitativo supporre che ogni femmina abbia risolto al più un’esercizio con m=1

Step 8: non è restrittivo supporre che ogni concorrente abbia risolto al più un esercizio con una coordinata =1.

Step 9: non è restrittivo supporre che gli esercizi con una coordinata pari ad uno siano in totale al più 3.

Step 10: conclusione.
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 16 giu 2006, 09:20

Ok. Finito! Già così, con gli enunciati degli step, è molto meglio. Bravo Enomis. Torna tutto.

Giusto per fare il pignolo (ma soprattutto, per cercare di insegnare qualcosina...) provo a limare due o tre punti oscuri.

Step. 4

Lo step 4 è cruciale, perché contiene l'idea chiave di tutta la dimostrazione: posso scambiare le soluzioni da un problema all'altro se uso certe accortezze. Questa medesima idea si usa da l' fino allo step 9, quindi è meglio che sia iper-chiara.

Provo a riscriverlo a modo mio:

Pre-step 4.1 Ogni m. ha risolto almeno un problema che ha almeno tre solutrici f.. Analogo risultato scambiando m. e f.

Dim.: Consideriamo, ad esempio, un maschio $ M $. Contiamo le soluzioni di $ M $ in comune con le ragazze. Per ipotesi tale numero deve essere almeno 21.

Però, se $ M $ avesse risolto solo esercizi con al più due solutrici, avrebbe risolto al massimo 12 esercizi in comune con le ragazze. []

Step 4 Non è restrittivo supporre che (3) sia vera, ossia che non esistano problemi risolti da esattamente due m. e due f.

Dim.: Chiamo $ P $ un problema risolto esattamente da due m. e due f., che indico con $ M_1, M_2, F_1, F_2 $.

Dimostro che posso modificare la situazione data con una per la quale le ipotesi restano vere, che (3) risulti vera, e che la tesi sia vera se e solo se lo era inizialmente.

Per il Pre-step 4.1, esistono quattro problemi $ Q_{M1}, Q_{M2}, Q_{F1}, Q_{F2} $, non necessariamente distinti tra loro, tali che $ Q_{M1} $ è risolto da $ M_1 $ e da almeno tre ragazze (e analoghi risultati per gli altri problemi). Si noti che $ P $ e $ Q_{**} $ devono essere distinti.

Opero le seguenti modifiche:
- Se $ F_1 $ ha risolto $ Q_{M1} $, non faccio nulla; altrimenti aggiungo $ F_1 $ ai solutori di $ Q_{M1} $.
- Se $ F_2 $ ha risolto $ Q_{M2} $, non faccio nulla; altrimenti aggiungo $ F_2 $ ai solutori di $ Q_{M2} $.
- Se $ M_1 $ ha risolto $ Q_{F2} $, non faccio nulla; altrimenti aggiungo $ M_1 $ ai solutori di $ Q_{F2} $.
- Se $ M_2 $ ha risolto $ Q_{F1} $, non faccio nulla; altrimenti aggiungo $ M_2 $ ai solutori di $ Q_{F1} $.
- Tolgo tutti i solutori da $ P $.

In questo modo si vede che:
- $ M_1, M_2, F_1, F_2 $ perdono una soluzione, ed eventualmente ne acquistano una, quindi non possono superare il limite di 6 soluzioni.
- Ogni coppia del tipo $ (M_*, F_*) $ risolve in comune almeno un problema $ Q_{**} $, quindi ogni coppia m-f continua ad avere almeno una soluzione in comune.
- Un problema $ Q_{**} $ ha almeno tre solutori m. e tre f. se e solo se li aveva anche prima della sostituzione, quindi non sto modificando la verità della tesi.
- Il problema $ P $ non ha più solutori e può essere eliminato senza perdere in generalità.

Mi sono cioè ricondotto ad un caso in cui le ipotesi contuinuano ad essere verificate, la tesi è vera se e solo se lo era inizialmente, ma con un problema in meno. Dato che i problemi sono in numero finito, ripetendo il ragionamento, ad un certo punto avrò eliminato tutti i problemi con esattamente due solutori maschi e due femmine. Quindi non è restrittivo supporre (3). []


Step 9
Contiene un'idea semplicissima, ma l'hai scritta in arabo antico, con influssi dal sanscrito...

Si poteva dire, ad esempio:

Dim. Step 9: Diciamo che gli esercizi sono S (per tenere la notazione dello Step 10).

Double-counting del numero di soluzioni di esercizi del tipo (1,k) e del tipo (k,1).

Ogni problema ha almeno $ 1 + k $ solutori, dove $ k \geqslant 11 $. I problemi sono $ S $, quindi ho almeno $ 12 S $ soluzioni.

Del resto, per Step 8, ogni studente ha risolto al più un esercizio di quei tipi, quindi le loro soluzioni sono al massimo quanti sono gli studenti, cioè 42.

Mettendo insieme, si ottiene $ S \leqslant 3 $. []


Step 10
E' tutto giusto e corretto, ma, per scarsa capacità mia, ho dovuto rifare i conti tre volte prima di convincermi che fossero giusti...

Li riscrivo qui, riorganizzando i conti:

Per alleggerire la notazione, indico con $ J $ la sommatoria dei $ j_i $ e con $ K $ quella dei $ k_i $.

Le relazioni che si usano sono queste:

$ 2J + K \geqslant 21^2 $ [double-counting sulle coppie solutore/solutrice dello stesso problema]

$ 2A + S + J + K \leqslant 252 = 21 \cdot 12 $ [double-counting sulle soluzioni]

$ S \geqslant 0 $ [ovvia]

$ K \geqslant 11 S $ [per il Passo 6]

Con queste, stimo $ 4A+4S $:

$ 4A+4S \leqslant ( 21 \cdot 24 - 2S - 2J - 2K) + 4S \leqslant $
$ . \quad \quad \leqslant 21 \cdot 24 + 2S - \left( 21^2 - K \right) -2K = $
$ . \quad \quad = 21 \cdot 3 + 2S - K \leqslant $
$ . \quad \quad \leqslant 63 + 2S - 11S = $
$ . \quad \quad = 63 - 9S \leqslant 63 $.

Ricordando che $ n= A + S $, si ricava che $ n \leqslant 16 $.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Rispondi