una gara un pò anomala

[salva90]

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

good work by salva

[Juggler]

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.

[salva90]

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

[platz]

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

[Juggler]

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

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

[salva90]

oddio, mi sa che ci stiamo incasinando
confermo che 12 e 18 funzionano (a parte che dovete trovare anche n )
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!

[Zoidberg]

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"!

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!

[platz]

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??

[salva90]

ok, bene zoidberg

[platz]

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

[Zoidberg]

A dir la verità non ho capito bene come si fa a tirar fuori la tua relazione...

[platz]

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??

[salva90]

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

[pi_greco_quadro]

Ps infatti la difficoltà vera stava proprio nella costruzione di uno dei due casi..

[enomis_costa88]

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!