IMO 2005 - Problema B3 [era: Problem 6]

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

IMO 2005 - Problema B3 [era: Problem 6]

Messaggio da enomis_costa88 » 17 lug 2005, 09:19

[Modificato il titolo, dopo aver cercato per un'ora il problema B3... M.]

Problem 6
In a mathematical competition in which 6 problems were posed to be participants, every two of these problems were solved by more than 2/5 of the contestants. Moreover, no contestant solved all the 6 problems. Show that there are at least 2 contestants who solved exactly 5 problems each.

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

Messaggio da enomis_costa88 » 17 lug 2005, 09:27

Stà notte l'ho passata praticamente in bianco per pensarci su..
Non è completa ma mi sembra un buon inizio soluzione.

Ogni coppia è stata risolta da mediamente K studenti.
$ K \ge 2/5 n; k(min) = [2/5 n]+1 $
Le coppie totali sono $ {6 \choose 2}=15 $
Ogni studente può risolvere max 10 coppie ovvero $ {5 \choose 2} $. Inoltre se uno studente ha risolto 10 coppie allora ha risolto 5 problemi. Gli studenti possono risolvere $ 0; {2 \choose 2};{3 \choose 2};{4 \choose 2};{5 \choose 2} $ .
Il totale delle “soluzioni alle coppie” è 15k.
Ogni studente ha dato mediamente $ \frac{15[2/5n]+15}{n} \ge \frac{15*2*n}{5n}=6 $
Media soluzioni alle coppie per studente è maggiore di 6= $ {4 \choose 2} $ per cui almeno uno studente ha risolto più di 6 coppie..e l’unica possibilità sopra le 6 sono le 10 e quindi 5 problemi.
Supponiamo ora di volere massimizzare le soluzioni alle coppie senza usare altri studenti con 10 coppie.. useremmo n-1 studenti con 6 coppie e uno con 10 ovvero 6n+4.

Se $ 15[2/5 n]+15 \ge 6n+4 $ allora abbiamo finito la dimos perché non bastano n-1 studenti con 6 coppie per pareggiare i conti e ce ne vogliono quindi almeno2..

Dimostro ora la disuguaglianza:
1)se $ n \equiv 0 (mod 5) n=5k $
$ 6*5k+4 \leq 15[2/5 5k]+15 $
ovvero $ 30k \leq 30k +15 $

2) $ n \equiv 1 (mod 5) n=5k+1 $
$ 6*5k+10 \leq 15[(10k+2)/5 ]+15 =30k+15 $

3) $ n \equiv 2 (mod 5) $ DA COMPLETARE (ciò che avevo scritto era errato..)

4) $ n \equiv 3 (mod5) n=5k+3 30k+22 \leq 15[(10k+6)/5]+15=30k+30 $

5) $ n \equiv 4 (mod 5) n= 5k+4 $
$ 30k+24+4 \leq 15[(10k+8)/5]+15=30k+30 $

EDIT ho riguardato ora e c'era un'errore nel caso $ n \equiv 2 (mod 5) $.. se qualcuno mi aiuta a concludere :wink:

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

Messaggio da enomis_costa88 » 17 lug 2005, 20:16

visto che nessuno si fa avanti..
Caso in cui $ n \equiv 2 (mod 5) $
provo a vedere prima i casi piccoli come n=7.
ipotizziamo che solo uno abbia risolto correttamente 5 esercizi. le soluzioni saranno (massimizzandone il numero..) 7*4+1=29
ogni problema ha minimo 3 solver in comune con gli altri (k(min)=[(14/5]+1=3).
sappiamo che ciascun problema è stato risolto mediamente da 29/6 solver. 5>29/6>4 quindi deve esistere almeno un problema con massimo 4 solver.
Analizziamo le coppie che questo problema forma con gli altri.
dobbiamo vedere se sapendo che ciascuno dei 4 solver si può ripetere negli altri problemi massimo 3 volte(a parte colui che ne ha risolti 5..) riusciamo a fare in modo che ci siano 3 soluzioni (almeno..) per ogni coppia:
ma visto che 3*4+1<3*5 esiste almeno un'altro solver con 5 problemi risolti.

Ora provo a generalizzare lo stesso ragionamento per gli altri numeri $ n \equiv 2 (mod 5) $ ; e n = 5k+2
intanto la media di solver per problema è: $ \frac{(5k+2)4+1}{6} $ e visto che non è mai intero (il numeratore non è mai $ \equiv 0 (mod 6) $ ) c'è almeno un probnlema con massimo $ [\frac{(5k+2)4+1}{6}] $solver.
ciascuno si può ripetere 3 volte a parte uno che può 4.
se ci sono 2k+1 (cioè il numero minimo di soluzioni comuni a due problemi) soluzioni comuni per ogni problema allora va tutto male e la th può essere falsa se non ci sono allora dovrei essere apposto.
la disuguaglianza da dimostrare diventa ora:
$ 3[\frac{(5k+2)4+1}{6}]+1<10k+5 $
ma anche questa non mi sembra sempre vera :x :cry: :? :!: :?:

certo che gradirei commenti (fossero anche critiche..) o aiuti..
Buona serata Simone

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

Messaggio da Marco » 19 lug 2005, 08:03

Dunque, non ho letto tutto per tutto. Fino alla fine del primo post, dove arrivi a dire che n=2 (m.5). Fin lì, ok. Dopo, però, evidentemente stai "buttando via" qualcosa, dato che già potresti dire che gli unici eventuali controesempi sono con un solutore a 5 risolti e tutti gli altri a 4 (altrimenti a 6N + 4 coppie non ci arrivi).

Mi sembra strano che devi litigare per ridimostrare che c'è un concorrente con quattro risolti: sono tutti così, tranne uno.

Finisco di leggere, poi ti dico; quando ho buttato giù la mia la posto.
[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 » 19 lug 2005, 08:15

o finalmente qualcuno che la prova(ero impaziente di vedere una soluzione)! io effettivamente mi sono un po' bloccato e penso dovrei ricominciare dalla fine del primo post..in ogni caso nel secondo quando dicevo che ci si ripete tre o quattro volte intendevo più quella dell'esercizio in analisi ovvero quattro o cinque in realtà..
ora stavo provando a vedere quando non vale la seconda diseguaglianza che conseguenze si hanno (caso n=12 per esempio) ovvero come devono essere gli altri solver(quelli non interessati dall'insieme in analisi)?

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

Messaggio da Marco » 19 lug 2005, 08:56

enomis_costa88 ha scritto:dobbiamo vedere se sapendo che ciascuno dei 4 solver si può ripetere negli altri problemi massimo 3 volte(a parte colui che ne ha risolti 5..) riusciamo a fare in modo che ci siano 3 soluzioni (almeno..) per ogni coppia:
ma visto che 3*4+1<3*5 esiste almeno un'altro solver con 5 problemi risolti.
Questo pezzo del ragionamento non l'ho capito (e, purtroppo, si tratta del passaggio chiave). Puoi riformularlo in maniera più chiara?
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

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

Messaggio da Marco » 19 lug 2005, 13:23

Ecco, come detto, la mia. Mi sembra una soluzione troppo fortunata, per essere vera. Ad ogni modo, sentite qui, ma state attenti, perché potrebbe starci la ca**ata!! Use at your own risk!!

------------------------------------------------------

Sia N il numero dei concorrenti e, per ogni k=0..6, f(k) sia il numero di concorrenti con esattamente k soluzioni. Per ipotesi f(6)=0 e

$ $\sum_{k=0}^6 f(k) = N $

Per una coppia di esercizi {i,j}, definisco g(i,j) come il numero di concorrenti che ha risolto i e j.

Per ipotesi,

$ $g(i,j) > \frac 2 5 N $

e, per il Teorema Fondamentale della Teoria dei Numeri (*), allora

$ $g(i,j) \geqslant \frac 2 5 N + \frac \delta 5 $,

ove $ \delta $ è un opportuno intero compreso tra 1 e 5. (per esser precisi è univocamente dato dalla classe mod 5 di N).

Double-counting su tutte le coppie di esercizi risolti:

$ $ \sum_{i,j} g(i,j) = \sum_{k=0}^6 \binom k 2 f(k) \geqslant 6N + 3 \delta $

Che, risolvendo per f(5), si riscrive come

(**) $ 4 f(5) \geqslant 6 f(0) + 6 f(1) + 5 f(2) + 3 f(3) + 3 \delta > 0 $.

Questo già prova che f(5) > 0. La tesi è f(5) > 1. Se fosse f(5) = 1, da (**) avrei

$ 0 \leqslant 6 f(0) + 6 f(1) + 5 f(2) + 3 f(3) \leqslant 4 - 3 \delta $.

Da questo si deduce che $ f(0) = f(1) = f(2) = f(3) = 0 $ e $ \delta = 1 $ (quest'ultima si verifica sse $ N \equiv 2 \pmod 5 $).

In altri termini, per avere f(5) = 1 deve essere che tutti i concorrenti hanno risolto 4 esercizi, tranne uno (quello "bravo") che ne ha risolti 5. Diciamo che l'esercizio non risolto da costui è il sesto. Divido il resto dei concorrenti a seconda se hanno risolto il sesto, oppure no. I primi formano l'insieme A, e i secondi il B. Con abuso di linguaggio, indicherò anche con A e B il numero di concorrenti nell'uno e nell'altro insieme. Chiaramente A + B + 1 = N.

Per finire, indicherò con a(i) e b(i) il numero di concorrenti in A e B che hanno risolto l'esercizio i, i che va da 1 a 5.

Distinguo le coppie di esercizi a seconda che contengano o meno l'esercizio 6 e rifaccio il double-counting. Le coppie "con" sono contate a tre a tre dai concorrenti di A (e quindi contano 3A volte in tutto). Le coppie "senza": il bravo ne ha collezionate 10, i concorrenti di A ne hanno 3, i concorrenti di B ne hanno 6.

Da cui:

$ $ \sum_{i=1}^5 g(i,6) = 3A \geqslant 5 \frac{2N+1}{5} $

$ $ \sum_{0<i<j<6} g(i,j) = 10 + 3A + 6B \geqslant 10 \frac{2N+1}{5} $

Queste si risolvono dando

$ $ A \geqslant \frac{2N+1}{3} \qquad B \geqslant \frac{N-5}{3} $

Però A e B sono necessariamente interi, mentre i membri di destra non è detto. In particolare, si vede che, se $ N \equiv 0 \pmod 3 $, la somma dei membri di destra arrotondati per eccesso supera N - 1; questo esclude di botto questo caso.

Negli altri due casi, invece gli arrotondamenti danno la somma giusta, e quindi possiamo dedurre:

$ $ A = \frac{2N+1}{3} \qquad B = \frac{N-4}{3} $, se $ N \equiv 1 \pmod 3 $;

$ $ A = \frac{2N+2}{3} \qquad B = \frac{N-5}{3} $, se $ N \equiv 2 \pmod 3 $.

Infine, osservo che il double-counting dice che tutte le coppie sono risolte da esattamente $ \frac{2N+1}{5} $ concorrenti ("coppie giuste"), eccetto una, che è risolta esattamente da $ \frac{2N+1}{5} + 1 $ ("coppia lunga").

Per comodità, da qui in poi pongo $ R:= \frac{2N+1}{5} $ (= il numero minimo di volte che una coppia deve comparire).

Vediamo i due casi:

Caso $ N \equiv 1 \pmod 3 $

Le coppie "con" sono tutte giuste, la coppia lunga è "senza".

Sia i=1..5. La coppia (i,6) è giusta, quindi a(i) = R.

Double-counting sulle coppie senza, contenenti i:

$ $ \sum_{j: i \neq j<6} g(i,j) = 2 a(i) + 3 b(i) = 2R + 3 b(i) = 4R [\textrm{o } 4R + 1] $

4R o 4R+1, a seconda che i non sia oppure sia nella coppia lunga.

Ma questa equazione non può valere 4R+1 (e lo si vede modulo 3, dato che in questo caso risulta sempre $ R \equiv 0 \pmod 3 $. Assurdo.

Caso $ N \equiv 2 \pmod 3 $

Stavolta la coppia lunga è "con", mentre le "senza" sono tutte giuste.

Se i appartiene alla coppia lunga, a(i) = R + 1; altrimenti a(i) = R.

Ripeto il ragionamento e trovo

$ $ \sum_{j: i \neq j<6} g(i,j) = 2 a(i) + 3 b(i) = 2( R [+1] ) + 3 b(i) = 4R [+ 1] $

(di nuovo, i "+1" ci sono nel caso di i appartenente alla coppia lunga). Stavolta è $ R \equiv 1 \pmod 3 $ e quindi, di nuovo, l'equazione non può valere mod. 3. Assurdo.

Per eccesso di scrupolo, dimostro anche che esiste una configurazione che soddisfa le ipotesi (ma con più di un concorrente a cinque soluzioni esatte) nel caso N>1.

[non credo che servisse nella soluzione "di gara", ma questo è un problema IMO, ed è buona norma non lasciare adito a dubbi che possano levare punti]

Per far questo, basta numerare i concorrenti e supporre che ogni concorrente abbia risolto tutti gli esercizi tranne quello della classe di resto del proprio numero d'ordine. E' facile verificare che, se N è almeno 2, tale configurazione soddisfa le ipotesi. []

(*) che recita che, se una quantità è intera e positiva, allora è almeno 1...
[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 » 19 lug 2005, 20:29

Questo è ciò che sono riuscito a fare oggi..ho il cervello che mi fuma letteralmente!!! e non so neppure esattamente se vi siano dei buchi o meno..

@marco: in quel passaggio (da cui è nata la seconda diseq..) io dicevo che con 4 solver (in un problema non totali..) non ne ho neppure abbastanza per coprire le intersezioni con gli altri problemi:
3*4+1=massimo numero di soluzioni date da quei 4 solver per gli "altri problemi" 3*5=intersezioni con gli "altri problemi" (con intersezioni intendo e intenderò in seguito soluzioni comuni)

Dimostro che la seconda disuguaglianza non vale(strettamente) solo se $ k \equiv 2 (mod 3) $

Essa dice che:
$ 3[ \frac{(5k+2)4+1}{6}]+1<10k+5 $
ora palesemente il numeratore non è mai pari per cui può essere $ \equiv $ 1,3,5 (mod 6)

1) $ (5k+2)4+1\equiv 1(mod 6) $
risolvendola si ottiene $ k \equiv 2 (mod 3) $ ; k=3g+2
sostituendo: si ottiene 30g+24<30g+24..falso!

2) se 20k+9 $ \equiv $ 3 (mod 6)
risolvendola k $ \equiv $ 0 (mod 3); k =3g
sostituendo: 30g+3<30g+4.

3) se 20k+9 $ \equiv $ 5 (mod 6);
k $ \equiv $ 1 (mod 3)k = 3g+1
e 30g+12<30g+14.
Quindi la seconda diseguaglianza non vale solo se k $ \equiv 2 (mod 3) $ e k= 3g+2.

Ottengo 5 problemi risolti da 10g+8 e uno da 10g+9(e visto che la disuguaglianza di prima valeva ma non strettamente se non fosse così varrebbe anche strettamente perché ci sarebbe un problema con meno solver visto che la media solver-quesito è fissa se tutti 4 e uno 5..e visto che nella diseq di prima si era detto che (le sol di un problema per 3)+1 non può essere minore di 5 volte le intersezioni senza convalidare la th..perchè non basterebbero neppure per coprire le intersezioni).

Ottengo: $ 60 g +49 \equiv 1 $ mod 6 per quanto dimostrato sopra. Quindi la media sarà 10g+8+1/6 e sapendo che nessun problema può essere risolto da meno di 10g+8 solver l’unica situazione possibile è quella descritta sopra.

Le intersezioni minime tra coppie di problemi sono 6g+5.
Ovvero 2k+1 e [2/5 n]+1.
I solver disponibili sono n ovvero 15g+12.
Fatto: per quanto detto sopra(disuguaglianza precedente) tutti i problemi con il numero minimo di solutori necessitano di un supersolutore(un cinesino che abbia vinto l’oro insomma con 5 soluzioni).

Analizziamo un problema tra questi 5: chiamiamolo A. esso avrà 6g+5 in comune con ciascun altro. Prendiamo l’insieme (leggesi problema) con 10g+9 ( lo chiamo B)e senza cinesino: questo avrà 6g+5 intersezioni con A. i suoi solver comuni con A si ripetono massimo 2 volte negli altri problemi (escluso A e se).il totale delle altre intersezioni con A è (espresso in k e non in g..) è 4(2k+1) e i suoi solver(di B e A..) si ripetono in questi per un totale di (2k+1)2..quindi le intersezioni da colmare sono 4(2k+1)-2(2k+1)=2(2k+1) = 4k+2 e espresso in g: 12g+10. quindi la media di intersezioni con B da creare(cioè che non c’erano con A)è $ \frac {12g+10}{4} $ .

Dopo che ho usato i solver di A mi rimangono 5g+4=n-( 10g+8 ) solver disponibili per i problemi successivi e in ciascun problema 6g+5 solver già occupati.
Uso ora i solver di B : mi rimangono g solver disponibili per i gruppi successivi e mediamente (se non è intero qualcuno di meno) 6g+5+ \frac {12g+10}{4}occupati. Ora ci sarà almeno un’insieme che ha occupato un numero minore o uguale a quello..prendo quell’insieme e lo analizzo: i solver disponibili(senza usarne di già usati e senza aumentare le intersezioni..) sono g ma mi sembra proprio che non bastino..

$ 6g+5+ \frac {12g+10}{4}+g<10g+8 $e questa mi sembra proprio vera..
per cui è impossibile non usarne di già usati e o si aumentano le intersezioni con A nel qual caso si verifica la seconda diseq o con B.

caso in cui aumentano le intersezioni con B:
se il gruppo(leggesi problema con più soluzioni) grande (B) ha più intersezioni del previsto allora ci sarà un gruppo piccolo con più intersezioni del previsto(non si interseca da solo)..e si verifica la seconda diseq perché essa ha a secondo membro 5(2k+1) che sono le intersezioni formate da un gruppo piccolo che aumenterebbero verificandola..


PS non so quante vaccate avrò sparato però sono molto contento di ciò che ho fatto..per me è la prima volta che affronto un problema di questa difficoltà e anche se non fosse tutto giusto sono felice :D :wink:

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

Messaggio da Marco » 21 lug 2005, 11:15

Mamma mia, Enomis, cerca di scrivere meglio!! Trucco: quando hai finito di scrivere la dimostrazione, cerca di leggerla "con gli occhi di un altro" (cioè senza dare per scontata tutta quella massa di idee che tu hai chiare perché ci hai sbattuto la testa a sufficienza, ma che per un altro sono ancora tutte da capire).

Quindi, se ho ben capito, la tua linea è:

Se la seconda diseguaglianza è vera, allora non può esistere il controesempio, perché c'è un problema con troppo pochi compagni.

Non so se hai notato, ma succede una cosa interessante: nella mia dimostrazione il caso "facile" era N=12 (mod. 15), che veniva escluso subito, mentre dovevo lavorare su N=2 e N=7. Nella tua, al contrario, N=2 e 7 sono facili, mentre devi trattare il caso N=12.

Ah, btw, ho visto che nella mia manca un "+4" in due punti abbastanza cruciali. Per fortuna che mod.3 gli errori si aggiustano. (se non è culo questo...)

Per il caso N=12, devo ancora vedere la tua sol. A dopo. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

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

Messaggio da Marco » 21 lug 2005, 14:03

Mmmmh... o non ho capito bene io, o c'è qualcosa che non torna.

Ti seguo solo fino a
enomis_costa88 ha scritto:Fatto: per quanto detto sopra(disuguaglianza precedente) tutti i problemi con il numero minimo di solutori necessitano di un supersolutore(un cinesino che abbia vinto l’oro insomma con 5 soluzioni).
e fino a qui ci siamo.

Poi però dici:
enomis_costa88 ha scritto:questo avrà 6g+5 intersezioni con A. I suoi solver comuni con A si ripetono massimo 2 volte negli altri problemi (escluso A e se).il totale delle altre intersezioni con A è (espresso in k e non in g..) è 4(2k+1) e i suoi solver(di B e A..) si ripetono in questi per un totale di (2k+1)2..quindi le intersezioni da colmare sono 4(2k+1)-2(2k+1)=2(2k+1) = 4k+2 e espresso in g: 12g+10. quindi la media di intersezioni con B da creare(cioè che non c’erano con A)è $ \frac {12g+10}{4} $ .

Se c'è qualcuno che ha capito, alzi la mano [e poi me lo spieghi].

Però mi pare che le intersezioni tra A e B sono almeno 6g + 5, ma non sai che sono esattamente 6g + 5. Se questo migliori o peggiori le cose non mi è chiaro (ma ho il forte sospetto che le peggiori).

E poi: "il totale delle altre intersezioni con A" Quali altre? Di tutti i non B con A? "si ripetono in questi" Questi quali? "le intersezioni da colmare" in che senso? "intersezioni con B da creare(cioè che non c’erano con A)" ???

Mi spiace, ma pure con tutta la buona volontà, non ti seguo proprio...

Steatt
Messaggi: 9
Iscritto il: 01 gen 1970, 01:00
Località: Roma

Messaggio da Steatt » 21 lug 2005, 16:34

Io l'ho risolto (purtroppo solo la sera dopo la gara) cosi, ma è la prima volta che lo scrivo per bene e potrebbe essere sbagliata:
Si dimostra facilmente che il numero degli studenti deve essere della forma 2+5k,e che tutti devono aver risolto 4 esercizi tranne almeno 1 che ne ha risolti 5. Bisogna dimostrare che è impossibile che 1+5k studenti risolvano 4 esercizi e 1 ne risolva 5. Ogni coppia dovrebbe essere stata risolta da almeno 2k+1 studenti, ma le coppie sono 6*(5k+1)+1*(10)=30k+16=(2k+1)*14+1*(2k+2), il che vuol dire che una coppia di problemi è stata risolta da 2k+2 studenti, e la altre 14 da 2k+1. Supponiamo che lo studente che ne ha risolti 5 non ha risolto l'1. Allora vi sono 2 casi: o la coppia piu risolta è una del problema 1, o una non del problema 1.
Nel primo caso (per esempio la coppia di problemi 1-2 è stata risolta da 2k+2 studenti), se consideriamo uno degli altri 4 problemi (uno a caso tra il 3,4,5,6, ad esempio il 3) otteniamo che la somma degli studenti che hanno risolto i problemi delle coppie 3-1,3-2,3-4,3-5,3-6 sono 5*(2k+1)-4=3x, in cui x è il numero di studenti (escluso quello bravo) che hanno risolto il problema 3. Inoltre se consideriamo il problema 1, e le coppie 1-2,1-3,1-4,1-5,1-6, abbiamo che (2k+1)*4+(2k+2)=3y, in cui y è il numero di studenti che ha risolto il problema 1. Ma dalla seconda ottiene k multiplo di 3 e dalla prima k congruo a 2. Quindo questo caso è impossibile. Nell' altro caso (esempio il bravo risolve tutti tranne l'uno e la coppia risolta da 2k+2 studenti è senza l'1, ad esempio la 2-3), si ha 5*(2k+1)=3y e 9*(2k+1)+1*(2k+2)-5=3x. Ma anche in questo caso non esiste k che le risolve entrambe. Quindi devono essere almeno 2 studenti che ne hanno risolti 5. Fatemi sapere se qualche passaggio non è chiaro.

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

Messaggio da Marco » 21 lug 2005, 19:02

Dunqui, dunqui, occhio e croce sembrerebbe la stessa mia idea (un po' più diretta, probabilmente ho dimostrato un po' troppa roba: che il primo caso si verifica sse N=7 e l'altro per N=2).

Di fatto, si guardano le coppie che coinvolgono un dato esercizio e si vede che non torna mod.3.

Ste, hai visto anche la prima idea di Enomis, per escludere N=2, 7 (mod. 15)? Secondo me non è affatto male [anche se la prosa espositiva lascia alquanto a desiderare...]
[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 » 21 lug 2005, 19:29

Mi spiace per la prosa espositiva..ma ciò che ho scritto è circa il riassunto di 12 paginette di idee,sproloqui e soprattutto disegni e schemi (usando gli insiemi mi sembra un pò più comprensibile).

Provo a riscrivere decentemente la parte incriminata..

Intanto ragiono con insiemi ed elementi che è più semplice..i problemi diventano insiemi e i solutori diventano elementi degli insiemi.
Osservo come si comporta un’insieme “piccolo” che chiamo A.
Se A ha più di 6g+5 =2k+1 elementi in comune con anche solo un’altro insieme (di meno non può averne..per ipotesi) allora succede una cosa molto simpatica (vale la seconda diseq e quindi la th è verificata); spiego meglio perché:
le intersezioni con gli altri insiemi(che sono 5)avrebbero un totale minimo di (6g+5)5+1 elementi ma il “materiale” disponibile(gli elementi degli insiemi) è di meno..
Gli elementi di A sono 10g+8(come spiegato sopra e se serve rispiegherò..) che possono stare in massimo (se la th fosse falsa) uno in 5 insiemi e gli altri in 4.
Quindi uno può stare in 4 insiemi oltre ad A e gli altri in 3 insiemi oltre ad A.
Questi elementi possono coprire massimo: 3(10g+8 )+1=30g+25 altre “intersezioni”. Ma quelle richieste sono 30g+26..da cui la validità della seconda diseq e della tesi.
Ora penso che siamo d’accordo che servono massimo (e minimo..) 6g+5 elementi in ogni intersezione.
Quindi anche l’insieme senza “l’elemento da 5 presenze” ovvero l’insieme con 10g+9 elementi avrà 6g+5 intersezioni con A.
Chiamo questo insieme B. Anche B deve avere 6g+5 elementi nelle altre intersezioni (adesso spiego..).
B è l’insieme grosso su cui non “vale” la seconda diseq anche se avesse un elemento in più nelle intersezioni. Però se B avesse anche solo un’intersezione con un’elemento in più allora esisterebbe un altro insieme ”piccolo” con un’elemento in più (e su questo varrebbe per il ragionamento di prima la seconda diseq..).
Voglio calcolare ora quanti tra gli elementi comuni ad A e ad B sono comuni anche ad altri insiemi.

Gli elementi comuni ad A,B possono stare in massimo altri 2 insiemi (in due ci sono già..e non possono in 5 perché B non ha il supersolutore).
Il totale delle intersezioni tra A e gli altri 4 insiemi è uguale a quello di B con gli altri 4 insiemi..ed è 4(2k+1) (espresso in k; ricordo che k=3g+2). Gli elementi comuni di A,B possono fare altre 2(2k+1) presenze negli altri 4 insiemi. O meglio se supponiamo che tutti gli elementi comuni tra A e B abbiano 4 presenze totali (di più non possono e se ne hanno di meno vale la seconda disequazione..se non capite chiedete) B ha quindi già 2(2k+1) elementi nelle sue altre intersezioni(nelle sue intersezioni con gli altri 4 insiemi). Il totale è 4(2k+1) e se ne ha già la metà glie ne servono altre
2(2k+1)=4k+2=12g+10.
Ovvero mediamente altre $ \frac {12g+10}{4} $ per ciascuno degli altri 4 insiemi.

Poi mi sembra che la conclusione sia più comprensibile..ma se chiedete riscrivo anche quello :lol:

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

Messaggio da Marco » 22 lug 2005, 08:55

Ok. Bravo Enomis!! Ora mi hai convinto e torna. Beh, allora, che effetto fa, risolvere un "IMO-6"?

Solo un commento: l'ultima parte della tua dimostrazione in effetti non serve. Quando arrivi a dire:
enomis_costa88 ha scritto:Quindi anche l’insieme senza l’elemento da 5 presenze ovvero l’insieme con 10g+9 elementi avrà 6g+5 intersezioni con A.
Qui hai di fatto già finito. Infatti, finora hai provato con successo che:

- N=12 (m.15)

- ci sono esattamente N-1 elementi in esattamente 4 insiemi e l'ultimo elemento (il cinesino bravo) in 5 insiemi

- c'è esattamente un insieme (B, il "sesto esercizio", nella mia terminologia) con un elemento in più (10g + 9) rispetto a tutti gli altri (che ne hanno 10g + 8)

- l'unico insieme che non contiene il cinesino è B

- ogni insieme diverso da B interseca ogni altro insieme in esattamente 6g + 5 (che è il minimo prescritto dalle ipotesi).

- il numero totale di intersezioni (contate con molteplicità) è esattamente 6N + 4 = 90g + 76.

Se metti insieme questi ultimi due alinea, concludi, perché:

-- le coppie di insiemi sono fatte da almeno un insieme che non è B.

-- la loro intersezione ha 6g + 5 (quindi ogni intersezione ha 6g + 5 elementi)

-- il numero totale di intersezioni è perciò 15(6g + 5) = 90g + 75. Te ne manca una all'appello!!!

Un saluto. Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Steatt
Messaggi: 9
Iscritto il: 01 gen 1970, 01:00
Località: Roma

Messaggio da Steatt » 22 lug 2005, 16:45

In realta avevo scritto il post di fretta senza leggere prima con cura le vostre soluzioni. Rileggendole bene (soprattutto quella di Marco) non sono molto diverse, anche se per capirle ci ho messo parecchio tempo.

Rispondi