una gara un pò anomala

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

una gara un pò anomala

Messaggio da salva90 » 16 ago 2007, 11:00

Ad una gara partecipano n studenti e vengono proposti m problemi. ogni studente risolve esattamente metà dei problemi, ed ogni problema viene risolto lo stesso numero di volte.
Inoltre, per ogni coppia di studenti, esattamente 3 problemi sono stati risolti da entrambi.
Determinare tutte le possibili copie (m, n)


l'ho ripescato stamani dalla gara a premi di parma, assicuro che non è cosi cattivo come la sua posizione nella lista lo farebbe sembrare :wink:

good work by salva :wink:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Juggler
Messaggi: 29
Iscritto il: 16 gen 2007, 15:59

Messaggio da Juggler » 16 ago 2007, 12:34

se non ho completamente frainteso tutti gli studenti risolvono tutti gli stessi problemi, perche' dato che hanno tutti risolto almeno 3 problemi uguali, questi sono stati risolti n volte, quindi l'unico modo per risolvere gli altri m/2-3 problemi n volte e' che ognuno degli studenti lo risolva.

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 16 ago 2007, 13:28

e l'ipotesi che ogni problema viene risolto lo stesso numero di volte dove la lasci?

non è che tutti risolvono gli stessi tre problemi, è che presi due ragazzi ci sono esattamente tre problemi risolti da entrambi

:wink:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

platz
Messaggi: 43
Iscritto il: 29 giu 2007, 20:33

Messaggio da platz » 16 ago 2007, 16:49

m è pari;
m/2 sono i problemi affrontati da ogni studente e (m/2)*n sono tutte le soluzioni date dagli n studenti;
inoltre ogni problema è stato risolto da n/2 studenti quindi anche n è pari.

Se ogni studente ha 3 problemi in comune con uno qualsiasi degli altri n-1 studenti allora avremo che 3*(n-1)=m/2
da cui deduciamo che $ m \equiv 0 (6) $ e $ n \equiv 1 (6) $
Da cui $ n=(m+6)\setminus6 $.

Così n sembra essere funzione di m e per m=12 e m=18 ho visto che il ragionamento regge e azzarderei a dire che n esiste per ogni m divisibile per 6 ..però sono pronto ad accettare confutazioni :wink:

Juggler
Messaggi: 29
Iscritto il: 16 gen 2007, 15:59

Messaggio da Juggler » 16 ago 2007, 17:34

platz ha scritto:m è pari;
m/2 sono i problemi affrontati da ogni studente e (m/2)*n sono tutte le soluzioni date dagli n studenti;
inoltre ogni problema è stato risolto da n/2 studenti quindi anche n è pari.

Se ogni studente ha 3 problemi in comune con uno qualsiasi degli altri n-1 studenti allora avremo che 3*(n-1)=m/2
da cui deduciamo che $ m \equiv 0 (6) $ e $ n \equiv 1 (6) $
Da cui $ n=(m+6)\setminus6 $.

Così n sembra essere funzione di m e per m=12 e m=18 ho visto che il ragionamento regge e azzarderei a dire che n esiste per ogni m divisibile per 6 ..però sono pronto ad accettare confutazioni :wink:
penso che la tua congettura sia vera ma in ogni caso 6,12,18 sono gli unici valori in quanto m deve essere minore od uguale a 18, consideriamo il primo studente, esso risolve m/2 problemi, il secondo studente ne risolve 3 comuni con il primo e m/2-3 diversi, quindi il terzo studente per soddisfare le ipotesi che deve avere *esattamente* 3 problemi in comune con ogni coppia ne fa 3 in comune con il primo, 3 con il secondo(consideriamo il caso in cui non siano tutti e 3 comuni tra i 3 studenti, in quanto sarebbe una condizione + riduttiva), quindi ora il terzo studente ha la sola possibilita' di fare altri 3 problemi(m - (m/2+m/2-3)) e quindi m<=18

p.s. con m=6 n puo' essere qualunque numero, infatti basta considerare che ognuno degli studenti faccia i primi 3 problemi e questo soddisfa le ipotesi.

Con il post precedente avrei in pratica dimostrato (c'è n'era bisogno?) che se gli studenti hanno tutti 3 problemi in comune e m diverso 6 porta a una contraddizione con le ipotesi :S

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 16 ago 2007, 19:46

oddio, mi sa che ci stiamo incasinando
confermo che 12 e 18 funzionano (a parte che dovete trovare anche n 8) )
però con 6 non mi quadra :?
basta considerare che ognuno degli studenti faccia i primi 3 problemi e questo soddisfa le ipotesi.
achtung! non soddisfa l'ipotesi perchè cosi alcuni problemi sono risolti più volte di altri!
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Avatar utente
Zoidberg
Messaggi: 312
Iscritto il: 10 mar 2006, 15:41
Località: Pisa - Trebaseleghe (PD)
Contatta:

Messaggio da Zoidberg » 16 ago 2007, 20:04

Io l'avevo risolto cosi...
Ma mi pare si discosti un po' dai vostri risultati!
Se qualcuno mi trova l'errore gliene sono grato!
Come gia detto m e n sono pari.

Se contiamo il numero totale di problemi risolti viene n*(m/2) e, dato che ci sono m problemi, ogni problema viene risolto n/2 volte!

Prendiamo uno studente a caso e chiamiamolo "Mitchan88"! :twisted:

Il povero Mitchan88 risolve m/2 problemi (chiaramente quelli più semplici!).

Ogni altro studente all'infuori di Mitchan per ipotesi ha risolto esattamente 3 di quei problemi, (che chiamerò problemi banali) quindi in totale il numero di problemi banali risolti è m/2 + 3*(n-1).

Dal lemmino di prima ogni problema è stato risolto n/2 volte quindi il numero di problemi banali rislti complessivamente è m/2*n/2.

Se uguagliamo i due risultati

m/2 + 3n - 3 = m*n/4

m e n sono pari quindi pongo m=2k e n=2x

k + 6x -3 =kx
6x-3= k (x-1)

k deve inoltre essere dispari come si vede chiaramente

Provo a sostituire a k i valori dispari

Le uniche soluzioni che ammettono x intero sono

k=7 x=4
k=9 x=2

quindi
m=14 n=8
m=18 n=4

Per la seconda ho trovato un esempio quindi va bene!
Per la prima non riesco a trovarlo ma non mi sembra improbabile che esista!

Membro dell'associazione "Matematici per la messa al bando dell'associazione "Matematici per la messa al bando del Sudoku" fondata da fph" fondata da Zoidberg

platz
Messaggi: 43
Iscritto il: 29 giu 2007, 20:33

Messaggio da platz » 16 ago 2007, 20:05

capito..
ora magari dico una ca****a assurda xk mi sembra banale, ma se m= 12 ho n=3 e se m=18 n=4 per la formula che ho scritto prima 3(n-1)=m/2..
right??

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 16 ago 2007, 20:07

ok, bene zoidberg :wink:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

platz
Messaggi: 43
Iscritto il: 29 giu 2007, 20:33

Messaggio da platz » 16 ago 2007, 20:16

Ma quindi m=14 è un risultato? perchè allora è sbagliata la relazione 3(n-1)=m/2...
perchè effettivamente alcuni problemi potrebbero essere comuni anche a una terna di studenti; in questo caso però credo che non tutti i problemi siano risolti lo stesso numero di volte

Avatar utente
Zoidberg
Messaggi: 312
Iscritto il: 10 mar 2006, 15:41
Località: Pisa - Trebaseleghe (PD)
Contatta:

Messaggio da Zoidberg » 16 ago 2007, 20:24

A dir la verità non ho capito bene come si fa a tirar fuori la tua relazione... :oops:
Membro dell'associazione "Matematici per la messa al bando dell'associazione "Matematici per la messa al bando del Sudoku" fondata da fph" fondata da Zoidberg

platz
Messaggi: 43
Iscritto il: 29 giu 2007, 20:33

Messaggio da platz » 16 ago 2007, 20:41

Dato che ogni studente risolve m/2 problemi e ne ha in comune 3 con ogni altro degli n-1 studenti abbiamo 3(problemi in comune)*(n-1)(tutti gli altri studenti)=m/2
a dire il vero avevo pensato che alcuni problemi potevano essere comuni a più di due studenti però in questo modo qualche problema riceverebbe più soluzioni degli altri..dov'è l'inghippo?? :(

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 16 ago 2007, 20:46

già che ci sono metto pure il mio conteggio...
appurato che m e n sono pari e che ogni problema è risolto da metà alunni metto m=2a e n=2b

a questo punto il primo studente risolve a problemi, che sono risolti complessivamente altre 3(2b-1) volte.
del resto metà problemi sono risolti complessivamente ab volte
quindi ho:
a+3(2b-1)=ab cioè a(b-1)=3(2b-1) da cui è agevole vedere che b-1|3, da cui le soluzioni :wink:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Avatar utente
pi_greco_quadro
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da pi_greco_quadro » 16 ago 2007, 20:50

Ps infatti la difficoltà vera stava proprio nella costruzione di uno dei due casi.. :P
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"

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

Messaggio da enomis_costa88 » 16 ago 2007, 20:53

Un'altro doppio conteggio diverso..

Piglio una tabella con n colonne e m righe.
Numero i problemi e numero le persone.
Metto una x nella casella (a,b) se la persona a esima ha risolto il problema b-esimo.

Conto la somma delle coppie di x sulla stessa riga.
Per ogni coppia di colonne avrò 3 coppie di x (ciascun elemento della coppia sulla stessa riga le 3 coppie su 3 righe diverse).

Quindi in tutto le coppie di x su ogni riga saranno $ 3 {n \choose 2} $

Però le coppie di x su ogni riga posso anche contarle riga per riga..
E' facile verificare che su ogni riga avrò s=n/2 x e quindi il numero di coppie sarà:
$ m{s \choose 2} $

da cui per doppio conteggio l'uguaglianza:
$ 3n(n-1)=ms(s-1) $
ovvero:
$ 6s(2s-1)=ms(s-1) $
da cui posto s-1=a
$ m=\frac{6(2a+1)}{a} $
e a divide 6 da cui le uniche soluzioni possibili sono:
a=6,3,2,1
s=7,4,3,2
n=14,8,6,4
m=13,14,15,18

Qualcuno ci ricorderà che m deve essere pari..e qualcun'altro di buona volontà verificherà se (14,8 ) e (18,4) fungono!
"Tu che lo vendi cosa ti compri di migliore?"

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

Rispondi