Problema archimedeo

[edriv]

Cercando di indovinare i problemi di domani... mi è venuto in mente questo:

Andrea è al biennio. Quanti saranno i possibili punteggi che farà domani ad Archimede?
A) 81
B) 90
C) 100
D) 101
E) Nessuna delle precedenti

Ok, ovviamente non è finita qui... generalizzare ad una gara in cui si fanno $ ~ a $ punti indovinando la risposta,$ ~ b $ lasciandola vuota e 0 sbagliandola, con un totale di x domande. Vedere anche cosa succede se si toglie il vincolo x.

Che poi questo è quel Bezout che Marco usa in questo problema:
http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=6902
Credo che si chiami anche teorema di Sylvester... che possiamo enunciarlo anche come "abbiamo solo monete da x euro o y euro. quali somme possiamo pagare?"

Insomma, risolvetelo!

[Cammy87]

Uhm ci ho pensato un po' in fretta, quindi potrei aver fatto qualche errore.
Comunque la risposta mi viene E, e precisamente 95 possibili punteggi.

Nella gara del biennio ci sono 20 domande, ogni risposta corretta vale 5 punti, ogni risposta bianca 1 punto e ogni risposta errata 0 punti. [lo scrivo perchè avevo fatto tutti i conti con punteggi diversi, prima di accorgermi che erano questi! ]

Indicando con X il punteggio di Andrea esso sarà della forma X=5*A+1*B. Dove A e B sono due interi (A= numero risposte corrette e B= numero risposte bianche) tali che A+B<21.
L'equazione precedente è una diofantea lineare che ha sempre soluzione per Bezout, poichè MCD(5,1)=1|X per qualsiasi X naturale. Bisogna però verificare in quali casi esistono A,B tali che A+B<21.
- Se X<85 esistono sempre A,B che soddisfano le richieste. Indico un procedimento per trovarli.
Sia N il più grande multiplo di 5 tale che N=<X, pongo A=N/5 e B=X-N.
Poichè X<85 allora A<17=85/5, quindi prendendo 0=<B<5, è verificata A+B<21 e posso ottenere tutti i punteggi compresi tra due multipli di 5.

[Cammy87]

- Nel caso X>=85, A>=17 e non posso ottenere tutti i numeri compresi tra due multipli successivi di 5. Per esempio se A=17 allora B<4 e non posso ottenere 89=17*5+4*1, perchè 17+4=21.
Con questo sistema si verifica facilmente che i numeri che non si possono ottenere sono soltanto 6. Quindi essendo 101 i potenziali punteggi (va incluso anche X=0), i punteggi ottenibili da Andrea sono 101-6=95.

Spero di essere stato abbastanza chiaro e di non aver fatto errori, vista l'ora tarda. Alla bonus question penserò con calma domani mattina, mentre voi sarete impegnati nei giochi di archimede ( un po' di nostalgia).
In bocca al lupo a tutti!!

P.S. Scusate il doppio post, mas e lasciavo il messaggio unito mi venivano troncate delle righe.

[SkZ]

Poniamo $ ~a>b $ (altrimenti avrebbe poco senso: nessuno risponderebbe alle domande!) e prendiamo $ ~a,b\in\mathbb{N}^* $ (per mia mera semplicita' ), definiamo il punteggio realizzabile $ ~p=a\xi+b\zeta $ con $ ~\xi+\zeta=x $ e $ ~c=a\mod{b} $ con ($ ~c\in [1;b-1] $ ovviamente) e $ ~d=\frac{a-c}{b}= \lfloor\frac{a}{b}\rfloor $ ($ ~d\ge 1 $ ovviamente).
Possiamo imporre $ ~MCD(a,b)=1 $ dato che se avessimo $ ~ MCD(a,b)=\epsilon\;\Rightarrow\; a=\alpha \epsilon,\; b=\beta \epsilon $ e i punteggi sarebbero del tipo $ ~ax+by=\epsilon(\alpha x+\beta y) $, quindi la soluzione di $ ~(a,b) $ e' riconducibile a quella di $ ~(\alpha,\beta) $

Se $ ~x\rightarrow\infty $ allora sono possibili tutti i punteggi maggiori di $ ~(a-1)(b-1) $ (i punteggi piu' piccoli non ci sono tutti: work in progress).


Se $ ~b=1 $ ci si riconduce al discorso di Cammy87:
$ ~\bullet ~x\ge a-1\Rightarrow $ sono possibili tutti i punteggi $ ~\in [0; xa-(a-1)(a-2)] $ e altri $ ~\frac{(a-2)(a-1)}{2} $ punteggi, in totale $ $1+xa- \frac{(a-1)(a-2)}{2}$ $ punteggi
$ ~\bullet ~x< a-1\Rightarrow $ sono possibili $ $\frac{(x+1)(x+2)}{2}$ $ punteggi