OliForum Matematico

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

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.

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

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

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

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

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!

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!

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

ok, bene zoidberg

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

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

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

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

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

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!

OliForum Matematico

una gara un pò anomala

una gara un pò anomala