Un problema sui... problemi
Ad una gara di matematica partecipano 21 ragazze e 21 ragazzi. Vale che:
1) Ogni ragazzo e ogni ragazza ha risolto al massimo 6 problemi.
2) Per ogni ragazzo A e per ogni ragazza B c'è un problema risolto sia da A sia da B.
Dimostrare che c'è un problema risolto da almeno 3 ragazzi e almeno 3 ragazze.
1) Ogni ragazzo e ogni ragazza ha risolto al massimo 6 problemi.
2) Per ogni ragazzo A e per ogni ragazza B c'è un problema risolto sia da A sia da B.
Dimostrare che c'è un problema risolto da almeno 3 ragazzi e almeno 3 ragazze.
Risposte
Nessuno ci prova?
Io ci provo; supponiamo che a quella gara ci fossero x problemi; il fatto che il problema sia rislto sia da un ragazzo che da una ragazza e che i partecipanti siano in egual modo ripartiti tra i due sessi mi spinge a non considerarne uno (consideriamo solo le ragazze) perche non ci sono altre relazioni che colleghino maschi e femmine. Quindi il problema si risolve a : se ho 21 partecipanti che hanno risolto 6 quesiti su x assegnati posso dimostrare che ce ne sono almeno 3 che hanno risolto lo stesso problema? E quante di loro saranno carine? Scusate non avevo letto gli ogni; mea maxima ciulpa. Ripartiamo da capo; se consideriamo una sestupla formata da tre ragazze e tre ragazzi si avra che in essa presi un ragazzo e una ragazza qualsiasi essi avranno un problema comune; devo trovare che esiste una sestupla formata da gente che ha risolto lo stesso problema.Mi spiace ma devo andare a lezione. Ciao
Be', naturalmente non ho niente da commentare... Il tuo, Salamandra, si chiama di solito "stream of consciousness"..
Proseguo lo stream of consciousness di Salamandra,
proprio a ruota libera...
Supponiamo che ci siano in ballo un bel po' di problemi
da risolvere.
Vediamo.
A[size=75]1[/size] ha in comune un problema con B[size=75]1[/size]... B[size=75]21[/size].
Poiché A[size=75]1[/size] può al massimo risolvere 6 problemi,
immaginiamo che con B[size=75]1[/size]... B[size=75]6[/size] abbia in comune 6
diversi problemi (più aumentano le persone coinvolte
in un medesimo problema, più è facile avvicinarsi alla
tesi e noi dobbiamo invece evitarlo). Questo significa
che con ciascun membro del gruppo B[size=75]7[/size]...B[size=75]21[/size] ha in
comune un problema già risolto con un membro
del gruppo B[size=75]1[/size]... B[size=75]6[/size].
Si può avere questa situazione, per esempio:
A[size=75]1[/size]: B[size=75]1[/size];B[size=75]7[/size],B[size=75]13[/size],B[size=75]19[/size] / B[size=75]2[/size];B[size=75]8[/size],B[size=75]14[/size],B[size=75]20[/size] / B[size=75]3[/size];B[size=75]9[/size],B[size=75]15[/size],B[size=75]21[/size] /
B[size=75]4[/size];B[size=75]10[/size],B[size=75]16[/size] / B[size=75]5[/size];B[size=75]11[/size],B[size=75]17[/size] / B[size=75]6[/size];B[size=75]12[/size],B[size=75]18[/size]
ma si può avere anche questa:
A[size=75]1[/size]: B[size=75]1[/size];B[size=75]7[/size],B[size=75]8[/size],B[size=75]9[/size],B[size=75]10[/size],B[size=75]11[/size],B[size=75]12[/size],B[size=75]13[/size],B[size=75]14[/size],B[size=75]15[/size],B[size=75]16[/size],B[size=75]17[/size],
B[size=75]18[/size],B[size=75]19[/size], B[size=75]20[/size], B[size=75]21[/size] / B[size=75]2[/size] / B[size=75]3[/size] / B[size=75]4[/size] / B[size=75]5[/size] / B[size=75]6[/size].
Vediamo comunque che ci sono almeno 3 B che hanno
in comune con A[size=75]1[/size] uno stesso problema.
Passiamo ad A[size=75]2[/size] e supponiamo che anch'esso abbia risolto
6 problemi distinti e diversi da quelli trattati da A[size=75]1[/size].
Quest'ipotesi ci permette di restare lontani dalla tesi,
evitando punti di contatto fra A[size=75]1[/size] e A[size=75]2[/size] e quindi fra
gli A e i B.
Come abbiamo visto sopra, esistono almeno 3 B che hanno
in comune con A[size=75]2[/size] un identico problema.
Facciamo lo stesso ragionamento con A[size=75]3[/size], che quindi tratta
6 problemi fra loro distinti e diversi da quelli di A[size=75]2[/size] e A[size=75]1[/size].
Anche in questo caso esistono almeno 3 B che hanno in
comune con A[size=75]3[/size] uno stesso problema.
Il discorso potrebbe filare fino ad A[size=75]6[/size]. Da A[size=75]1[/size] ad A[size=75]6[/size], i 6
problemi che legano un certo A a ciascun B cambiano.
Con A[size=75]7[/size], però, non possiamo ricorrere a dei nuovi problemi
perché, se così facessimo, qualche B risolverebbe più di
6 problemi.
Questo ci porta a dire che A[size=75]7[/size] si trova a trattare i problemi
già affrontati da A[size=75]1[/size]...A[size=75]6[/size] e, di conseguenza, dai B (secondo
una certa ripartizione).
Se A[size=75]7[/size] avesse un problema in comune con A[size=75]1[/size], per esempio,
esisterebbero senz'altro almeno due coppie di A e B, diciamo
A[size=75]1[/size]-B[size=75]i[/size] e A[size=75]7[/size]-B[size=75]j[/size], accomunate dallo stesso problema (abbiamo
detto che esistono almeno 3 B che hanno in comune con A[size=75]1[/size]
un problema, quindi, se A[size=75]7[/size] e A[size=75]1[/size] avessero in comune lo stesso
problema, ci sarebbero non meno di 3 B, nella peggiore delle
ipotesi, che condividerebbero quel problema pure con A[size=75]7[/size] e
perciò troveremmo senz'altro due distinte B accoppiabili
ad A[size=75]1[/size] e A[size=75]7[/size] ).
Ora, sempre per restare il più lontano possibile dalla tesi,
supponiamo che A[size=75]1[/size]-A[size=75]7[/size], A[size=75]2[/size]-A[size=75]8[/size], A[size=75]3[/size]-A[size=75]9[/size], A[size=75]4[/size]-A[size=75]10[/size], A[size=75]5[/size]-A[size=75]11[/size] e
A[size=75]6[/size]-A[size=75]12[/size] siano legate da un problema (un problema diverso
per ciascuna coppia).
Cosa succede quando passiamo ad A[size=75]13[/size]?
Succede questo: che saltano fuori 3 A che hanno in comune
uno stesso problema e, poiché per ogni A ci sono 3 B, nel caso
più limitato avremmo 3 B che hanno trattato lo stesso problema
condiviso dalle 3 A.
Caro Fields, la tua ineguagliabile abilità espressiva e logica,
a questo punto, potrebbe tremolicchiare di fronte a ciò che
ho scritto (se non inorridire!), però non volevo lasciarti
dondolare di nuovo verso il largo.
Ovviamente, spero di non aver postato sviste o errori
madornali, ma devo fare i conti con il poco tempo.
proprio a ruota libera...
Supponiamo che ci siano in ballo un bel po' di problemi
da risolvere.
Vediamo.
A[size=75]1[/size] ha in comune un problema con B[size=75]1[/size]... B[size=75]21[/size].
Poiché A[size=75]1[/size] può al massimo risolvere 6 problemi,
immaginiamo che con B[size=75]1[/size]... B[size=75]6[/size] abbia in comune 6
diversi problemi (più aumentano le persone coinvolte
in un medesimo problema, più è facile avvicinarsi alla
tesi e noi dobbiamo invece evitarlo). Questo significa
che con ciascun membro del gruppo B[size=75]7[/size]...B[size=75]21[/size] ha in
comune un problema già risolto con un membro
del gruppo B[size=75]1[/size]... B[size=75]6[/size].
Si può avere questa situazione, per esempio:
A[size=75]1[/size]: B[size=75]1[/size];B[size=75]7[/size],B[size=75]13[/size],B[size=75]19[/size] / B[size=75]2[/size];B[size=75]8[/size],B[size=75]14[/size],B[size=75]20[/size] / B[size=75]3[/size];B[size=75]9[/size],B[size=75]15[/size],B[size=75]21[/size] /
B[size=75]4[/size];B[size=75]10[/size],B[size=75]16[/size] / B[size=75]5[/size];B[size=75]11[/size],B[size=75]17[/size] / B[size=75]6[/size];B[size=75]12[/size],B[size=75]18[/size]
ma si può avere anche questa:
A[size=75]1[/size]: B[size=75]1[/size];B[size=75]7[/size],B[size=75]8[/size],B[size=75]9[/size],B[size=75]10[/size],B[size=75]11[/size],B[size=75]12[/size],B[size=75]13[/size],B[size=75]14[/size],B[size=75]15[/size],B[size=75]16[/size],B[size=75]17[/size],
B[size=75]18[/size],B[size=75]19[/size], B[size=75]20[/size], B[size=75]21[/size] / B[size=75]2[/size] / B[size=75]3[/size] / B[size=75]4[/size] / B[size=75]5[/size] / B[size=75]6[/size].
Vediamo comunque che ci sono almeno 3 B che hanno
in comune con A[size=75]1[/size] uno stesso problema.
Passiamo ad A[size=75]2[/size] e supponiamo che anch'esso abbia risolto
6 problemi distinti e diversi da quelli trattati da A[size=75]1[/size].
Quest'ipotesi ci permette di restare lontani dalla tesi,
evitando punti di contatto fra A[size=75]1[/size] e A[size=75]2[/size] e quindi fra
gli A e i B.
Come abbiamo visto sopra, esistono almeno 3 B che hanno
in comune con A[size=75]2[/size] un identico problema.
Facciamo lo stesso ragionamento con A[size=75]3[/size], che quindi tratta
6 problemi fra loro distinti e diversi da quelli di A[size=75]2[/size] e A[size=75]1[/size].
Anche in questo caso esistono almeno 3 B che hanno in
comune con A[size=75]3[/size] uno stesso problema.
Il discorso potrebbe filare fino ad A[size=75]6[/size]. Da A[size=75]1[/size] ad A[size=75]6[/size], i 6
problemi che legano un certo A a ciascun B cambiano.
Con A[size=75]7[/size], però, non possiamo ricorrere a dei nuovi problemi
perché, se così facessimo, qualche B risolverebbe più di
6 problemi.
Questo ci porta a dire che A[size=75]7[/size] si trova a trattare i problemi
già affrontati da A[size=75]1[/size]...A[size=75]6[/size] e, di conseguenza, dai B (secondo
una certa ripartizione).
Se A[size=75]7[/size] avesse un problema in comune con A[size=75]1[/size], per esempio,
esisterebbero senz'altro almeno due coppie di A e B, diciamo
A[size=75]1[/size]-B[size=75]i[/size] e A[size=75]7[/size]-B[size=75]j[/size], accomunate dallo stesso problema (abbiamo
detto che esistono almeno 3 B che hanno in comune con A[size=75]1[/size]
un problema, quindi, se A[size=75]7[/size] e A[size=75]1[/size] avessero in comune lo stesso
problema, ci sarebbero non meno di 3 B, nella peggiore delle
ipotesi, che condividerebbero quel problema pure con A[size=75]7[/size] e
perciò troveremmo senz'altro due distinte B accoppiabili
ad A[size=75]1[/size] e A[size=75]7[/size] ).
Ora, sempre per restare il più lontano possibile dalla tesi,
supponiamo che A[size=75]1[/size]-A[size=75]7[/size], A[size=75]2[/size]-A[size=75]8[/size], A[size=75]3[/size]-A[size=75]9[/size], A[size=75]4[/size]-A[size=75]10[/size], A[size=75]5[/size]-A[size=75]11[/size] e
A[size=75]6[/size]-A[size=75]12[/size] siano legate da un problema (un problema diverso
per ciascuna coppia).
Cosa succede quando passiamo ad A[size=75]13[/size]?
Succede questo: che saltano fuori 3 A che hanno in comune
uno stesso problema e, poiché per ogni A ci sono 3 B, nel caso
più limitato avremmo 3 B che hanno trattato lo stesso problema
condiviso dalle 3 A.
Caro Fields, la tua ineguagliabile abilità espressiva e logica,
a questo punto, potrebbe tremolicchiare di fronte a ciò che
ho scritto (se non inorridire!), però non volevo lasciarti
dondolare di nuovo verso il largo.
Ovviamente, spero di non aver postato sviste o errori
madornali, ma devo fare i conti con il poco tempo.
Bruno, devo dire che il tuo ragionamento non è del tutto formale e fatico a seguirlo. Ad esempio, non seguo questa parte del tuo ragionamento (non mi risulta chiara).
Infatti dici che i ragazzi $A_1$ e $A_7$ hanno in comune uno stesso problema P: è vero. Chi ti dice che però questo problema non sia stato risolto da una sola donna? (questo naturalmente comporterebbe l'impossibilità di trovare le coppie distinte $A_1-B_i$ e $A_7-B_j$)
ps: Insisto sulla formalità del ragionamento non per pedanteria, ma perché in problemi come questo è facilissimo fare errori.
Se A7 avesse un problema in comune con A1, per esempio,
esisterebbero senz'altro almeno due coppie di A e B, diciamo
A1-Bi e A7-Bj, accomunate dallo stesso problema (abbiamo
detto che esistono almeno 3 B che hanno in comune con A1
un problema, quindi, se A7 e A1 avessero in comune lo stesso
problema, ci sarebbero non meno di 3 B, nella peggiore delle
ipotesi, che condividerebbero quel problema pure con A7 e
perciò troveremmo senz'altro due distinte B accoppiabili
ad A1 e A7 ).
Infatti dici che i ragazzi $A_1$ e $A_7$ hanno in comune uno stesso problema P: è vero. Chi ti dice che però questo problema non sia stato risolto da una sola donna? (questo naturalmente comporterebbe l'impossibilità di trovare le coppie distinte $A_1-B_i$ e $A_7-B_j$)
ps: Insisto sulla formalità del ragionamento non per pedanteria, ma perché in problemi come questo è facilissimo fare errori.
Fields... tu non hai ragione, ma una SUPER RAGIONE!
Si tratta di una clamorosa, macroscopica svista!
La fretta (e il poco tempo) ha fatto saltar via la
mia ruota (libera) dall'asse...
Vedo se riesco a trovare qualche minuto per
riprendere il bandolo della questione.
Si tratta di una clamorosa, macroscopica svista!
La fretta (e il poco tempo) ha fatto saltar via la
mia ruota (libera) dall'asse...
Vedo se riesco a trovare qualche minuto per
riprendere il bandolo della questione.
No, caro Fields: sarà stata l'ora di pranzo, ma quello
che ho scritto non mi fa arrivare proprio a nulla.
Mannaggia: mi tocca ripartire da zero, spero di poterlo
fare.
Volo!
Ciao
che ho scritto non mi fa arrivare proprio a nulla.
Mannaggia: mi tocca ripartire da zero, spero di poterlo
fare.
Volo!
Ciao
Ok, buon lavoro! (se avrai tempo per continuarlo )
)
'Sto giochino è peggio di una zanzara...
Non ho molto tempo da dedicargli, però ogni volta che lo vedo ci riprovo e... niente.
Mi ci vorrebbe un po' più di tempo (ad averlo!)
Pac
Non ho molto tempo da dedicargli, però ogni volta che lo vedo ci riprovo e... niente.
Mi ci vorrebbe un po' più di tempo (ad averlo!)
Pac
'Sto giochino è peggio di una zanzara...
Eh, eh, l'ho postato apposta
Comunque penso che valga la pena provare ad affrontarlo
Domanda idiota: se nessuno ha risolto un problema?
Impossibile per la proprietà 2).
D' oh. 
Comunque a naso io lo dimostrerei per 1 problema solo e poi per induzione dimostro che esiste sempre un problema risolto da 3 ragazzi e 3 ragazze. (induzione sul numero dei problemi, nel nostro caso indefinito)
Comunque a naso io lo dimostrerei per 1 problema solo e poi per induzione dimostro che esiste sempre un problema risolto da 3 ragazzi e 3 ragazze. (induzione sul numero dei problemi, nel nostro caso indefinito)
Innanzitutto si potrebbe limitare il problema: dato che ogni persona ha risolto al massimo 6 problemi e supponendo che siano tutti diversi possiamo dire che al massimo i problemi risolti sono 2*21*6=252. Dato che tra ogni coppia ragazzo e ragazza c' e' un problema comune si ha che nell' insieme tra un ragazzo e tutte le ragazze ci sono al massimo 111 problemi diversi, perche' il ragazzo ne ha risolti 6 e ogni ragazza solo altri 5 diversi, quindi 6+5*21=111. Invertendo le parti si ha che 111 problemi sono stati risolti nell' insieme ragazza- ragazzi; se noi ora consideriamo l'insieme completo non ci sono 222 problemi, perche' : prendiamo una ragazza e abbiamo 6 problemi; se aggiungiamo un ragazzo ne abbiamo 11; se aggiungiamo un'altra ragazza ne abbiamo 11+5=16; se aggiungiamo un ragazzo ne abbiamo 16+4; se aggiungiamo una ragazza ne abbiamo 20+4=24; se aggiungiamo un ragazzo 24+3=27; se aggiungiamo una ragazza 27+3=30; se aggiungiamo un ragazzo 30+2=32; se aggiungiamo una ragazza 32+2=34; ragazzo 34+1=35; ragazza 35+1=36; ragazzo 36+0=36; ragazza 36+0= 36. Ora questo e' un conto che vale sul massimo numero di problemi e che ho fatto ipotizzando che non ci siano problemi comuni tra le ragazze. Tuttavia facendo conti sui numeri piccoli (2 ragazzi e 2 ragazze) mi sembra che cio' valga in generale (chiedo aiuto a chi ha piu' conoscenze di me in insiemistica e affini). Se si potrebbe dimostrare che in realta' i problemi risolti sono al massimo k si potrebbe dimostrare l'indovinello per k, visto che e' il caso peggiore. Anche se temo che cio' sia una strada impraticabile. Spero comunque che mi abbiate seguito nel ragionamento abbastanza tortuoso, altrimenti cerchero' di essere piu' chiaro. Ciao
Be' Salamandra, non credo che la tecnica di limitazione sul numero dei problemi possa funzionare... Ho calcolato che ci possono essere ben 211 problemi diversi risolti in totale. Comunque ti rassicuro su un fatto: il problema in questione non richiede nessuna conoscenza particolare, e uno studente di terza media ha le conoscenze sufficienti per risolverlo. Certo il ragionamento da fare è un minimo sofisticato..
Comunque anch'io ho utilizzato, fra le altre cose, un metodo di limitazione, ma non direttamente sul numero dei problemi...
Comunque anch'io ho utilizzato, fra le altre cose, un metodo di limitazione, ma non direttamente sul numero dei problemi...
"fields":
2) Per ogni ragazzo A e per ogni ragazza B c'è un problema risolto sia da A sia da B.
Intendi che c'e' un SOLO poblema risolto sia da A sia da B?
Sicuramente ho capito male, perche' se si fa risolvere ad ogni ragazzo ed ad ogni ragazza lo stesso problema, le due condizioni sono soddisfatte. E chiaramente e' vero che c'e' almeno un problema risolto da almeno 3 ragazzi e 3 ragazze.
"Crook":
[quote="fields"]2) Per ogni ragazzo A e per ogni ragazza B c'è un problema risolto sia da A sia da B.
Intendi che c'e' un SOLO poblema risolto sia da A sia da B? [/quote]
Il testo dice che esiste un problema P risolto da A e da B, ma non impone che P sia l'unico problema ad essere stato risolto sia da A sia da B.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo