Quesito di Gara a squadre....

[Julito]

Salve,
mi sto cimentando nella scrittura "didattica" delle soluzioni delle gare a squadre di Cesenatico 2013, e non riusciamo a venire a capo del seguente quesito:
13. Un attimo di pausa
Dopo essersi sfidati sul campo di battaglia, il Giaguaro e il Ronzino si rilassano insieme a Radice prendendo un tè. Aitka, il cappellaio, offre
loro 94 biscotti, numerati da 1 a 94. Il Re Bianco ordina a Radice di mangiarne un certo numero intero a, al Giaguaro b, e al Ronzino c.
Chiaramente a,b,c>=0 e a+b+c = 94. “Curioso—nota Aitka—il numero di modi diversi in cui potete dividervi i biscotti rispettando gli
ordini del Re è multiplo di 3”. Quante terne ordinate (a;b;c) hanno questa proprietà?

La soluzione banale che otteniamo è 4560, e sembra soddisfare tutte le condizioni. Tuttavia la soluzione fornita dagli autori è 4479.

Qualcuno sarebbe disposto a discutere la soluzione?
Noi abbiamo ragionato così:
per a=0 , per b e c si ottengono 95 coppie ordinate;
per a=1 , per b e c si ottengono 94 coppie ordinate;
....
per a=94, per b e c si ottiene 1 sola coppia ordinate;
dunque sommando i primi 95 naturali si ottiene 95x96/2= 4560
Lo stesso risultato di ottiene con Cn+k-1,k-1

Dove sbagliamo???

P.S.: Siamo dei docenti di scuola superiore, appassionati dei giochi olimpici, e ci battiamo per la divulgazione della matematica in tutte le sue forme. Grazie mille, in ogni caso.

[Gi8]

Non bisogna contare tutte le possibili terne.Bisogna contare quelle valide, cioè quelle terne $(a,b,c)$ (con $a,b,c$ interi non negativi tali che $a+b+c=94$) per cui si abbia che il numero di modi di dare i $94$ biscotti ai tre tizi col vincolo di darne $a$ al primo, $b$ al secondo e $c$ al terzo sia un numero divisibile per $3$.

Per esempio la terna $(0,0,94)$ non è valida, perchè i tre tizi possono dividersi i biscotti in $1$ modo e $1$ non è divisibile per $3$.
Quindi certamente il Re Bianco non può avere detto a Radice di mangiare $0$ biscotti, a Giaguaro $0$ e a Ronzino $94$.

Invece la terna $(0,2,92)$ è valida:
il numero di modi di dare i $94$ biscotti ai tre col vincolo di darne $0$ a Radice, $2$ a Giaguaro e $92$ a Ronzino è $\binom{94}{2}= 4371$, che è divisibile per $3$.


Spero di essermi spiegato

[Julito]

Quindi, per calcolare la soluzione devo controllare tutte le terne, o meglio trovare un modo per controllarle velocemente?
Dunque non esiste un modo con una formula unica?
Credo di aver capito questo.
Grazie tante.

[auron95]

Il problema probabilmente sta nel fatto che non tutte le 4560 terne così trovate soddisfano l'ultimo punto, cioè che i modi in cui possano dividersi i biscotti sia multiplo di 3: ad esempio per $(94,0, 0)$ esiste solo un modo in cui i tre possono dividersi i biscotti, ossia tutti i biscotti a Radice.

In generale se abbiamo generici $ a, b, c $ il numero di modi in cui possono dividersi i biscotti è:

$\binom {94} a $ modi per radice di prendere $ a $ biscotti, per $\binom {94-a}b $ modi di scegliere $ b$ biscotti tra i rimanenti.
Svolgendo i conti abbiamo $\displaystyle \frac {94!}{a! b! c!} $ modi, e questa quantità deve essere un multiplo di 3.

Ora con un po di casi si possono eliminare le terne per cui ci sono tanti fattori 3 al denominatore quanti ce ne sono al numeratore, facendo alcune osservazioni (ad esempio che tra i fattori sotto deve esserci un 81, altrimenti non ne avrei abbastanza....)

P.S battuto sul tempo

[Drago96]

Qua c'è una generalizzazione, ma sinceramente non so quali siano le difficoltà nel dimostrare il caso particolare e quello generale...

EDIT: Sì la formula è quella e pensandoci un attimo forse c'è un modo abbastanza agevole (che è quello della generalizzazione, sfruttando la rappresentazione in base 3), che è la formula di Legendre-De Polignac (nome altisonante per dire una cosa tutto sommato banale) e la disuguaglianza con la somma di parti intere...

[Julito]

OK! Ho capito.... adesso sarà complicato scriverlo in modo tale da essere capito di ragazzi delle prime classi. Un grande GRAZIE.
Buon Anno a tutti.

[Julito]

La formula di legendre-De Polignac era prevista nella risoluzione di quesito di finale, ma era più semplice individuarne l'uso... mi è venuta una bella idea grazie a Voi, vedrò di scrivere bene la soluzione... Mille Grazie.

[Julito]

Usando la formula di Legendre-De Polignac, si calcola che 3^45 divide 94!
Adesso sapendo che di diversi modi in cui la terna (a,b,c) si può formare prendendo i biscotti sono dati da 94!/(a!b!c!) [*]
Partendo dalle 3560 terne possibili, andiamo ad escludere quelle che non soddisfano la condizione che il numero di modi di costituirle sia multiplo di 3,
quindi a!b!c! deve essere divisibile per 3^45, dunque (analizzando le terne in cui a>=b , b=<c, e ottenendo per permutazione tutti i casi):
Se a=94 b=0 c=0 a!b!c! è divisibile per 3^45 (calcolando sempre con la formula di Legendre- De Polignac) quindi escludiamo 3 casi (permutando)
Se a=93 b=0 c=1 a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
Se a=92 b=0 c=2 a!b!c! NON è divisibile per 3^45, ma per 3^44
b=1 c=1 a!b!c! NON è divisibile per 3^45, ma per 3^44
Se a=91 b=0 c=3 a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
b=1 c=2 a!b!c! NON è divisibile per 3^45, ma per 3^44
Se a=90 b=0 c=4 a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
b=1 c=3 a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
b=2 c=2 a!b!c! NON è divisibile per 3^45, ma per 3^44
Se a=89 nessun caso escluso
Se a=88 nessun caso escluso
Se a=87 nessun caso escluso
Se a=86 nessun caso escluso
Se a=85 b=0 c=9 a! è divisibile per 3^41 e c! per 3^4, dunque a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
b=1 c=8 a!b!c! NON è divisibile per 3^45, ma per 3^43
b=2 c=7 a!b!c! NON è divisibile per 3^45, ma per 3^43
b=3 c=6 a!b!c! NON è divisibile per 3^45, ma per 3^44
b=4 c=5 a!b!c! NON è divisibile per 3^45, ma per 3^43
Se a=84 b=0 c=10 a! è divisibile per 3^41 e c! per 3^4, dunque a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
b=1 c=9 a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
per gli altri valori di b e c nessun caso escluso
Se a=83 nessun caso escluso
se a=82 b=0 c=12 a! è divisibile per 3^40 e c! per 3^5, dunque a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
b=3 c=9 a! è divisibile per 3^40, b! per 3 e c! per 3^4, dunque a!b!c! è divisibile per 3^45 quindi escludiamo 6 casi (permutando)
per gli altri valori di b e c nessun caso escluso
Se a=81 b=0 c=13 escludiamo 6 casi (permutando)
b=1 c=12 escludiamo 6 casi (permutando)
b=3 c=10 escludiamo 6 casi (permutando)
b=4 c=19 escludiamo 6 casi (permutando)
nessun caso escluso
Se 46<a<81 non ci sono più casi esclusi in quanto come facilmente si può notare in quanto già a! è divisibile per 3^36 e le altre combinazioni di b e c non permettono di raggiungere una divisibilità per 3^45 per a!b!c!

Riassumendo 4560-81=4479

Grazie a tutti coloro che sono intervenuti. Secondo voi la soluzione è scritta in modo comprensibile per alunni delle scuole superiori (con esperienza in giochi matematici) di biennio e triennio?

Ancora saluti e BUON 2K14
Giulio

[Drago96]

Provo a spiegare come lavorare sfruttando la scrittura in base 3 di 94 (che è 10111), a mio parere più istruttiva (e nemmeno troppo difficile da capire) di un lavoro a casi molto lungo...
Vogliamo contare i casi in cui $ v_p (94!)=v_p (a! b! c!)=v_p (a!)+v_p (b!)+v_p (c!) $. Sfruttiamo ora la scrittura in base 3: $94=3^4+3^2+3^1+3^0 $. Immaginiamo di scrivere anche $ a, b, c $ in base 3 (e $ a_i, b_i, c_i $ sono le loro cifre in posizione i-esima) e ovviamente la loro somma deve dare 94; supponiamo che facendo l'addizione in colonna ci sia un "riporto" e vediamo come questo influisce sulle valutazioni 3-adiche: se ci fosse un riporto vorrebbe dire che $ a_i+b_i+c_i\ge3 $ per un qualche $ i $; ma ciò allora implicherebbe che $\left\lfloor\frac{a+b+c}{3^{i+1}}\right\rfloor=(a_k+b_k+c_k)3^{k-i-1}+...+(a_{i+1}+b_{i+1}+c_{i+1})+\left\lfloor\frac {a_i+b_i+c_i }{3}+\frac {\text {termini piccoli}}{3^{i+1}}\right\rfloor=$
$=(a_k+b_k+c_k)3^{k-i-1}+...+(a_{i+1}+b_{i+1}+c_{i+1})+1> $
$>(a_k3^{k-i-1}+...+a_{i+1})+(b_k3^{k-i-1}+...+b_{i+1})+(c_k3^{k-i-1}+...+c_{i+1})=$
$= \left\lfloor\frac{a}{3^{i+1}}\right\rfloor+\left\lfloor\frac{b}{3^{i+1}}\right\rfloor+\left\lfloor\frac{c}{3^{i+1}}\right\rfloor$
Ovvero nel numeratore ci sono più 3 che al denominatore, cosa che noi non volevamo...
Quindi nell'addizione in colonna non ci sono riporti e quindi $ a_i+b_i+c_i=n_i $; con un conteggio standard sappiamo che le possibili scelte per le tre cifre sono $\binom {n_i+2}{2} $, e ovviamente le varie cifre sono indipendenti quindi si devono moltiplicare tutti i binomiali.
Nel caso di 94, bisogna moltiplicare $\binom{3}{2}\binom{2}{2}\binom{3}{2}\binom{3}{2}\binom{3}{2}=3^4=81 $

Si noti infine come i casi esclusi nel conteggio manuale sono appunto tutti e soli quelli senza il riporto

Aggiungo inoltre questo: http://www.cut-the-knot.org/wiki-math/i ... resFormula
E tutto questo fa vedere che le barbose trasformazioni di un numero da una base ad un'altra in realtà nascondano parecchie sorprese (a proposito, il teorema di Lucas è davvero una cosa bella! )

[Julito]

Bene, vedrò di semplificare quanto spiegatomi, e prepararmi il terreno per poterlo spiegare, anche se il cambio di base e le equivalenze modulari le abbiamo trattate.

[fph]

FYI, era uno dei problemi più difficili della gara.