compito di mate

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

49 ragazzi fanno un compito di matematica che comprende 3 esercizi
<BR>ad ognuno di questi (esercizi) viene dato un punteggio intero da 0 a 7 inclusi
<BR>dimostrare che esistono due studenti tali che uno ha tutti i tre voti maggiori o uguali all\'altro
<BR>
<BR>mi sa di principio dei cassetti, ma oltre a dire che x ogni esercizio c\'è almeno un voto \"condiviso\" da almeno 7 alunni, non ci ho tirato fuori + niente, e di fare tutti i vari casi non ne ho voglia
<BR>
<BR>qualche idea brillante? <IMG SRC="images/forum/icons/icon_wink.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: talpuz il 01-11-2003 14:23 ]
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
W28
Messaggi: 448
Iscritto il: 01 gen 1970, 01:00
Località: Tra Castellammare e Napoli

Messaggio da W28 »

Trovata :se ci sono io ho 0-0-0 e tutti i miei compagni 7-7-7 <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> [addsig]
Voglio sapere come Dio ha creato questo mondo voglio sapere i suoi pensieri tutto il resto è dettaglio (A.Einstein)
Avatar utente
W28
Messaggi: 448
Iscritto il: 01 gen 1970, 01:00
Località: Tra Castellammare e Napoli

Messaggio da W28 »

beh ... l\'ultimo compito almeno la sufficienza me la devono mettere !!!
<BR>
<BR>ho avuto il coraggio di risolvere su due problemi l\'esercizio più difficile e sbagliare quello uguale fatto il giorno prima in classe !!!
<BR>
<BR>E poi per la prima volta ho risolto tre diseguazioni (e per giunta logaritmiche) senza nessun errore di calcolo: <IMG SRC="images/forum/icons/icon_smile.gif"> [addsig]
Voglio sapere come Dio ha creato questo mondo voglio sapere i suoi pensieri tutto il resto è dettaglio (A.Einstein)
matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager »

E\' molto contorto, lungo e casinoso, comunque...
<BR>Sicuramente se c\'e\' un voto che e\' stato preso da 9 o piu\' persone non ci sono problemi, perche\' al secondo problema, per il principio dei cassetti, almeno due di quelle persone devono aver ripreso lo stesso voto e con due voti uguali, il gioco e fatto.
<BR>Ora, sapendo che il numero di persone che prendono uno stesso voto non puo\' superare 9, possiamo dire che ci sono sempre almeno sei voti che sono stati presi da almeno 6 ragazzi (perche\' al massimo ci sono sei voti con 8 persone). Ma, per il motivo di prima, i ragazzi che hanno preso lo stesso voto al primo esercizio devono prendere voti diversi al secondo e al terzo. Ora, pero\' facciamo un esempio:
<BR>
<BR>sei ragazzi che hanno preso lo stesso voto al 1 es, in modo tale che nessuno soddisfi la proprieta che cerchiamo di dimostrare:
<BR>
<BR>ragazzi 1 2 3 4 5 6
<BR>1 esercizio x x x x x x voto x uguale
<BR>2 esercizio 7 5 4 3 1 0
<BR>3 esercizio 1 2 3 5 6 7
<BR>
<BR>E\' chiaro che in generale i voti devono essere prima ascendenti e poi discendenti, altrimenti i voti presi da uno sarebbero entrambi maggiori (o minori) di quelli presi da un altro. Inoltre, poiche\' i voti possibile sono 8 e i ragazzi 6, due voti non saranno presi da nessuno.
<BR>Per questo abbiamo che la somma dei due voti rimanenti puo\' essere:
<BR>
<BR>5 ottenibile in 6 modi diversi (7,2; 6,1; 5,0; 0,5; 1,6; 2,7)
<BR>6 ottenibile in 7 modi diversi
<BR>7 ottenibile in 8 modi diversi
<BR>8 ottenibile in 7 modi diversi
<BR>9 ottenibile in 6 modi diversi
<BR>
<BR>il numero di voti possibili che possono prendere quei ragazzi al 2 e 3 esercizio e\' 34. poiche\' i ragazzi che avevamo preso in considerazione erano 36, per il principio dei cassetti 2 ragazzi prendono lo stesso voto al 2 e 3 es. <BR><BR>[ Questo Messaggio è stato Modificato da: matthewtrager il 03-11-2003 15:40 ]
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-11-03 15:39, matthewtrager wrote:
<BR>Ora, sapendo che il numero di persone che prendono uno stesso voto non puo\' superare 9, possiamo dire che ci sono sempre almeno sei voti che sono stati presi da almeno 6 ragazzi
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ecco, purtroppo questo e\' falso. Anche il resto della soluzione non mi convince...
<BR>
<BR>Propongo questa generalizzazione, che forse puo\' chiarire le idee sul caso particolare:
<BR>
<BR>Se i punteggi possibili sono 2n, i ragazzi sono 3n<sup>2</sup>+1.
<BR>Se i punteggi possibili sono 2n+1, i ragazzi sono 3n(n+1)+2.
<BR>La tesi e\' la stessa.[addsig]
matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager »

oops! hai ragione! <IMG SRC="images/forum/icons/icon_cool.gif"> <IMG SRC="images/forum/icons/icon27.gif">
matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager »

Allora ci riprovo... Mi mancavano un paio di casi!!
<BR>
<BR>Abbiamo gia\' detto che con un \"gruppo\" di 9 (9 persone che prendono lo stesso voto al primo es) due persone prendono sempre lo stesso voto al primo e al secondo es. e allora una delle due prendera\' un voto maggiore o uguale dell\'altro nel terzo.
<BR>
<BR>Se ci sono 2 gruppi di 8, invece, si ha che per non aver nessuna persona con voti \"confrontabili\"(chiamo cosi\' la proprieta\' che bisogna dimostrare per fare piu\' presto) all\'interno dei due gruppi, al secondo e al terzo esercizio le persone devono aver preso voti tutti diversi, e quindi tutti i voti possibili per ogni es, e in modo che la loro somma sia sempre 7, poiche\' devono essere:
<BR>
<BR>1esercizio) x x x x x x x x (uguali)
<BR>2esercizio) 7 6 5 4 3 2 1 0
<BR>3esercizio) 0 1 2 3 4 5 6 7
<BR>
<BR>altrimenti due saranno sempre confontabili. Poiche\' i gruppi da 8 erano due, sicuramente due persone (in realta\' 8 ) avranno preso gli stessi voti al 2 e 3 es quindi sono confrontabili.
<BR>
<BR>Se ci sono 4 gruppi da 7, si fa piu\' o meno lo stesso ragionamento di prima. I voti che prendono i ragazzi di un gruppo devono essere diversi per ciascuno dei due esercizi rimanenti e ancora dovranno essere in un caso discendenti e nell\'altro ascendenti (ora pero\' ci sara un buco)
<BR>
<BR>1esercizio) x x x x x x x (uguali)
<BR>2esercizio) 7 6 5 3 2 1 0
<BR>3esercizio) 0 1 2 4 5 6 7
<BR>
<BR>Come avevo fatto nella prima risoluzione, abbiamo che le somme dei punteggi possono essere
<BR>
<BR>6 in 7 modi diversi
<BR>7 in 8 modi diversi
<BR>8 in 7 modi diversi
<BR>
<BR>Totale: 22. Poiche\' nei quattro gruppi c\'erano 28 ragazzi, 2 avranno preso gli stessi voti al 2 e al 3 es.
<BR>
<BR>Poi c\'e\' il caso con 6 gruppi da 6, che e\' uguale. (e\' anche il caso che avevo fatto prima)
<BR>
<BR>Alla fine di tutto questo rimane un solo caso, con i seguenti gruppi (cioe\' in cui gli 8 voti nel primo es sono stati presi da): 8 7 7 6 6 5 5 5 (persone)
<BR>
<BR>Pero\' adesso sappiamo che devono esserci questi 8 gruppi, e usiamo sempre lo stesso trucco. la somma puo\' essere:
<BR>
<BR>4 in 5 modi
<BR>5 in 6 modi
<BR>6 in 7 modi
<BR>7 in 8 modi
<BR>8 in 7 modi
<BR>9 in 6 modi
<BR>10 in 5 modi
<BR>
<BR>Somma totale: 44. Ci sono 49 persone.
<BR>
<BR>[ Questo Messaggio è stato Modificato da: matthewtrager il 07-11-2003 17:45 ]<BR><BR>[ Questo Messaggio è stato Modificato da: matthewtrager il 07-11-2003 17:46 ]
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

ok, grazie matthew, adesso ci dò un\'okkiata
<BR>comunque penso che esista una soluzione un po\' + rapida, e soprattutto \"generalizzabile\"
<BR>(se invece che 7, 3 e 49 i numeri fossero stati + alti, contare tutti i vari casi sarebbe stato un suicidio!! <IMG SRC="images/forum/icons/icon_razz.gif"> )
<BR>...altre idee?
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

UP!
<BR>please, guardateci...
<BR>anche UN INPUT da parte di chi sa come si risolve l\'esercizio non sarebbe male...
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
mola6
Messaggi: 220
Iscritto il: 01 gen 1970, 01:00
Località: Rimini

Messaggio da mola6 »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-11-03 15:24, W28 wrote:
<BR>
<BR>E poi per la prima volta ho risolto tre diseguazioni (e per giunta logaritmiche) senza nessun errore di calcolo: <IMG SRC="images/forum/icons/icon_smile.gif"> [addsig]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>non si dice diseQuazioni?
"Per perdere la testa, bisogna innanzi tutto averne una!" A. Einstein
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-11-07 17:44, matthewtrager wrote:
<BR>Se ci sono 2 gruppi di 8, [...] al secondo e al terzo esercizio le persone devono aver preso voti tutti diversi, e quindi tutti i voti possibili per ogni es, e in modo che la loro somma sia sempre 7
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Dando per buono questo (che comunque si dimostra senza problemi...), mancano lo stesso un bel po\' di casi, ad esempio 8 7 7 7 6 6 5 3.
<BR>Ad ogni modo, sarebbe piu\' bello trovare una soluzione facilmente generalizzabile, e che non si perda tra miriadi di casi!<BR><BR>[ Questo Messaggio è stato Modificato da: Antimateria il 11-11-2003 02:39 ]
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>anche UN INPUT da parte di chi sa come si risolve l\'esercizio non sarebbe male...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>... <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif"> ...<BR><BR>[ Questo Messaggio è stato Modificato da: talpuz il 10-11-2003 20:03 ]
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria »

Talpuz, non so se ti riferissi a me con quella richiesta di input, comunque tutto quello che posso dire è che affinchè 48 persone abbiano voti non confrontabili occorre che siano disposte secondo l\'\"esagono\" che si ottiene intersecando il cubo con uno dei due \"piani di simmetria\" della diagonale (0,0,0) (7,7,7). Da qui scaturisce la mia congettura di generalizzazione, che si ricava calcolando l\'area dell\'esagono generico in funzione del lato.
<BR>
<BR>Semplicemente ho visto che la disposizione è sempre accettabile, che per n=8 l\'area è proprio il nostro 48, e che facendo un po\' di prove, sembra che i 48 tizi stiano bene solo sull\'esagono. Ma da qui a dimostrare tutto come si deve, il passo non è certo breve, almeno per me!
matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-11-10 16:49, Antimateria wrote:
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-11-07 17:44, matthewtrager wrote:
<BR>Se ci sono 2 gruppi di 8, [...] al secondo e al terzo esercizio le persone devono aver preso voti tutti diversi, e quindi tutti i voti possibili per ogni es, e in modo che la loro somma sia sempre 7
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Dando per buono questo (che comunque si dimostra senza problemi...), mancano lo stesso un bel po\' di casi, ad esempio 8 7 7 7 6 6 5 3.
<BR>Ad ogni modo, sarebbe piu\' bello trovare una soluzione facilmente generalizzabile, e che non si perda tra miriadi di casi!
<BR>
<BR>[ Questo Messaggio è stato Modificato da: Antimateria il 11-11-2003 02:39 ]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>scusa, ma l\'esempio che dici tu l\'ho analizzato perche\' 87776653 e\' compreso nel caso di quattro 7, e anche nel caso di sei 6.
<BR>
<BR>comunque sono d\'accordo che sarebbe meglio trovare un\'altra soluzione.<BR><BR>[ Questo Messaggio è stato Modificato da: matthewtrager il 11-11-2003 14:05 ]
LB
Messaggi: 72
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da LB »

L\'idea fondamentale è quella di dividere l\'insieme dei risultati possibili in 48 sottoinsiemi tali che, data una coppia qualunque di risultati nello stesso sottoinsieme essi siano comparabili.
<BR>
<BR>Dimostrato questo, per il pigeonhole esistono due studenti con i risultati nello stesso sottoinsieme, che è la tesi.
<BR>
<BR>Innanzitutto osserviamo che due risultati con la stessa somma sono sempre uguali o incomparabili e quindi devono stare in sottoinsiemi diversi.
<BR>Se m è il voto massimo, allora i risultati con somma floor/ceil(3/2m) sono quelli in massimo numero, mentre andando verso 0 e 3m il numero di risultati con la stessa somma decresce.
<BR>
<BR>Occorre quindi dimostrare che è possibile associare ogni risultato di somma s ad uno di somma s - 1 posto s > 3/2m e che è possibile associare ogni risultato di somma s ad uno di somma s + 1 posto s < 3/2m in modo che essi siano comparabili.
<BR>
<BR>Dimostrando questo, si possono costruire gli insieme partendo dai risultati con s = floor/ceil(3/2m).
<BR>
<BR>L\'associazione può essere fatta nel seguente modo:
<BR>Sia (a, b, c) il risultato con somma s e f(a, b, c) quello con somma s - 1.
<BR>
<BR>Se a >= s - m e c < s - m, allora f(a, b, c) = (a, b - 1, c).
<BR>Se a < s - m e b > 2m - s, allora f(a, b, c) = (a, b, c - 1).
<BR>Se b <= 2m - s e c >= s - m (c > b), allora f(a, b, c) = (a - 1, b, c).
<BR>
<BR>Innanzitutto, (a, b, c) deve ricadere in uno di questi casi poichè altrimenti si ottiene a + b + c < s o a + b + c > s e inoltre (a, b, c) > (d, e, f).
<BR>
<BR>f(a, b, c) non ha valori negativi perchè:
<BR>Nel primo caso, se b = 0, si avrebbe a + b + c < s
<BR>Nel secondo caso, se c = 0, si avrebbe a + b + c < s
<BR>Nel terzo caso, se a = 0, si avrebbe a + b + c <= 3m - s. Ma 3m - s < s poichè s > 3/2m, quindi a + b + c < s.
<BR>
<BR>Inoltre ovviamente f(a,b,c) != f(d,e,f) se (a,b,c) != (d,e,f) ed entrambe ricadono nello stesso caso.
<BR>
<BR>f(a,b,c) != f(d,e,f) se (a,b,c) != (d,e,f) anche per casi differenti perchè le disuguaglianze relative al membro immutato hanno sempre verso opposto.
<BR>
<BR>Quindi l\'associazione funziona.
<BR>
<BR>Per quanto riguarda s < 3/2m, possiamo osservare che (a, b, c) < (d, e, f) <=> (m - a, m - b, m - c) > (m - d, m - e, m - f) e quindi ricondurci alla dimostrazione per s > 3/2m.
<BR>
<BR>Rimane da dimostrare che il numero di sottoinsiemi è <= 48.
<BR>
<BR>A tale scopo, cerchiamo un espressione per f(m,p,s) che è il numero di p-uple di interi in [0, m] con somma s.
<BR>
<BR>Ricorsione:
<BR>
<BR>p >= 0 e s >= 0: f_m(p, s) = sum(i = 0 -> m) f_m(p - 1, s - i) + [p = 0][s = 0]
<BR>p < 0 o s < 0: f_m(p, s) = 0
<BR>
<BR>
<BR>Sia F_m la funzione generatrice di f_m.
<BR>
<BR>F_m = sum(i = 0 -> m) F_m * x * y^i + 1
<BR>
<BR>F_m = F_m x sum(i = 0 -> m) y^i + 1
<BR>
<BR>M = m + 1
<BR>G_M = F_m+1
<BR>g(M,p,s) = f(m + 1, p, s)
<BR>
<BR>G_M = G_M x (y^M - 1)/(y - 1) + 1
<BR>
<BR>
<BR>G_M = 1/(1 - x * (1 - y^M)/(1 - y))
<BR>
<BR>
<BR>sum(P, S) g_M(p, s) x^p y^s
<BR>
<BR>
<BR>G_M = sum x^i ((1 - y^M)/(1 - y))^i
<BR>
<BR>G_M,p = ((1 - y^M)/(1 - y))^p
<BR>
<BR>G_M,p = (1 - y^M)^p * 1/(1 - y))^p
<BR>
<BR>G_M,p = sum(i = 0 -> p) {(p i) (-1)^i y^iM} * sum(i = 0 -> inf) {(i + p - 1 p - 1) * y^i}
<BR>
<BR>G_M,p = sum(i = 0 -> p, j = 0 -> inf) {(p i) (j + p - 1 p - 1) (-1)^i y^(iM + j)}
<BR>G_M,p = sum(i = 0 -> p, j = 0 -> M, k = 0 -> inf) {(p i) (kM + j + p - 1 p - 1) (-1)^i y^(iM + kM + j)}
<BR>G_M,p = sum(i = 0 -> p, j = 0 -> M, k = 0 -> inf) {(p i) (kM + j + p - 1 p - 1) (-1)^i y^((i + k)M + j)}
<BR>G_M,p = sum(i = 0 -> min(p, n), j = 0 -> M, n = 0 -> inf) {(p i) ((n - i)M + j + p - 1 p - 1) (-1)^i y^(nM + j)}
<BR>G_M,p = sum(i = 0 -> min(p, floor(o/M)), o = 0 -> inf) {(p i) (o - iM + p - 1 p - 1) (-1)^i y^o}
<BR>G_M,p = sum(s = 0 -> inf) {sum(i = 0 -> min(p, floor(s/M))) {(p i) (s - iM + p - 1 p - 1) (-1)^i} y^s}
<BR>
<BR>g(M, p, s) = sum(i = 0 -> min(p, floor(s/M))) {(p i) (s - iM + p - 1 p - 1) (-1)^i}
<BR>
<BR>*****
<BR>f(m, p, s) = sum(i = 0 -> min(p, floor(s/(m + 1)))) {(p i) (s - i(m + 1) + p - 1 p - 1) (-1)^i}
<BR>*****
<BR>
<BR>Applichiamola ora al nostro problema:
<BR>
<BR>f(m, 3, floor(3m/2)) = sum(i = 0 -> min(3, floor(floor(3m/2)/(m + 1)))) {(3 i) (floor(3m/2) - i(m + 1) + 3 - 1 3 - 1) (-1)^i}
<BR>
<BR>per m >= 2, p >= 1:
<BR>f(m, 3, floor(3m/2)) = sum(i = 0 -> 1) {(3 i) (floor(3m/2) - i(m + 1) + 3 - 1 3 - 1) (-1)^i}
<BR>
<BR>*****
<BR>m = 0 (2): f(m, 3, floor(3m/2)) = 1 + 3m/2 + 3m^2/4
<BR>m = 1 (2): f(m, 3, floor(3m/2)) = 3/4 + 3m/2 + 3m^2/4
<BR>*****
<BR>
<BR>f(7, 3, 10) = 48
<BR>
<BR>Abbiamo concluso.
<BR>
<BR>Manca ora la generalizzazione ad un numero di esercizi maggiore di 3. L\'idea migliore credo sia trovare una f(a, b, c, ...) usando una schema per casi simile a quello di f(a, b, c), ma non possiedo ancora una soluzione di ciò.
<BR>
Bloccato