Problema semifinale a squadre 2013

[emacoder]

Abbiamo 94 biscotti numerati da 1 a 94, Radice ne mangia a, Giaguaro b e Ronzino c. $a,b,c>=0$ e $a+b+c=94$. Quante sono le terne ordinate con questa proprietà?

[enrico_s]

Consideriamo 94 palline e due sbarre.
La risposta alla domanda è data da tutti i diversi modi in cui posso disporre le due sbarre prima, in mezzo, o dopo delle palline;
cioè gli "anagrammi" di questa serie di elementi

Le terne sono $ \frac {96!}{2!94!}=4560 $

Però mi sembra che il problema richiedesse altro, perché quando l'avevo fatto avevo dovuto fare dei ragionamenti sui fattori 3. Sbaglio?

[emacoder]

Il testo dei problema è questo, però in effetti quella risposta non è corretta. Il tuo è il ragionamento classico che era venuto in mente subito anche a me, però non so perchè non funziona. Tu hai la soluzione completa?

[enrico_s]

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$ \geq $ 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à?

hai dimenticato questo dettaglio
vuol dire che di quelle 4560 terne devi considerare sole quelle per cui
$ \binom{94}{a}\binom{94-a}{b}\binom{94-a-b}{c}=3k $
che a intuito sono la maggior parte , quindi per trovare quante sono è conveniente contare quelle che non danno un valore multiplo di tre e sottrarle dal totale.

Noto innanzitutto che , poiché $ c=94-a-b $,
$ \binom{94-a-b}{c}=\binom{c}{c}=1 $

Quindi a me basta che $ \binom{94}{a}\binom{94-a}{b}\neq 3k $

Suppongo $ a\leq b \leq c $

$ \binom{94}{a}=\frac{94\cdot 93 \cdot ... \cdot (94-a+1)}{1\cdot 2 \cdot ... \cdot a} $

A questo punto considero su due righe quanti fattori 3 i numeri $ 94 , 93 , ... $ e $ 1,2,... $ mettono in campo

$ \begin{matrix} 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 4 & 0 & 0 & 1 & ...\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & ... \end{matrix} $

Se $ a+b\geq 14 $ allora al numeratore viene preso il numero 81 che mette 4 fattori 3.
Dunque affinché si semplifichino tutti quei 3, $ a $ e $ b $ dovrebbero essere tanto grandi, incompatibile con $ a\leq b \leq c $
(Non è una dimostrazione rigorosa ma trattandosi di una gara a squadre non importa come si arriva al risultato )

Ora dalle righe che ho scritto sopra vedo che gli unici valori accettabili per $ a $ sono $ 0,1,3,4 $

1) $ a=0 $

$ b= 0,1,3,4,9,10,12,13 $

Da cui le terne $ (0,0,94),(0,1,93),(0,3,91),(0,4,90),(0,9,85),(0,10,84),(0,12,82),(0,13,81) $

2) $ a=1 $

$ b=3,9,12 $

Da cui le terne $ (1,3,90),(1,9,84),(1,12,81) $

3) $ a=3 $

$ b=9,10 $

Da cui le terne $ (3,9,82),(3,10,81) $

4) $ a=4 $

$ b=9 $

Da cui la terna $ (4,9,81) $

A questo punto tolgo la condizione $ a\leq b \leq c $ e quindi per ogni terna conto le sue permutazioni
CASI SFAVOREVOLI TOTALI: $ 13\cdot 6 + 3= 81 $ (il 3 viene da (0,0,94) )

Quindi la risposta al problema è $ 4560-81=4479 $ che era effettivamente la soluzione

Spero si capisca abbastanza

[emacoder]

Ma cosa cambia se ti dice che il numero di modi è multiplo di 3? è solo un affermazione aggiuntiva che ti assicura che il tuo risultato dovrà essere multiplo di 3, ma non ti dice niente sulle tenre in se' a mio parere, o almeno, io lo leggo cosi...

[Lasker]

@emacoder: il testo ti sta dicendo che il Re Bianco sceglie gli interi $a,b,c$ da qui in poi fissati, a questo punto i tre possono spartirsi i biscotti in tot modi grazie al fatto che sono diversi (ad esempio, mettiamo che $a=0$, $b=1$, $c=93$, i modi in cui possono spartirseli sono $94$). Da qui in poi, il fatto che Aika dica che il numero di modi è multipo di tre, ti permette di scartare alcune terne $a,b,c$ dalle possibilità (tra cui proprio quella che ho scritto, perché $94$ non è multiplo di $3$).
P.S. non c'era una soluzione (che mi pareva avesse scritto Drago da qualche parte, ma che non riesco assolutamente a ritrovare ) che diceva tipo: scrivo $94$ in base $3$ ($10111$), conto gli "uni" (sono $4$) e tolgo dalle "combinazioni con le stanghette" proprio il valore $3^{4}$, o qualcosa del genere?

[enrico_s]

Non capisco, perché il fatto che 94 abbia 4 "1" in base 3 ti porta a escludere 81 ?

[emacoder]

@emacoder: il testo ti sta dicendo che il Re Bianco sceglie gli interi $a,b,c$ da qui in poi fissati, a questo punto i tre possono spartirsi i biscotti in tot modi grazie al fatto che sono diversi (ad esempio, mettiamo che $a=0$, $b=1$, $c=93$, i modi in cui possono spartirseli sono $94$). Da qui in poi, il fatto che Aika dica che il numero di modi è multipo di tre, ti permette di scartare alcune terne $a,b,c$ dalle possibilità (tra cui proprio quella che ho scritto, perché $94$ non è multiplo di $3$).
P.S. non c'era una soluzione (che mi pareva avesse scritto Drago da qualche parte, ma che non riesco assolutamente a ritrovare ) che diceva tipo: scrivo $94$ in base $3$ ($10111$), conto gli "uni" (sono $4$) e tolgo dalle "combinazioni con le stanghette" proprio il valore $3^{4}$, o qualcosa del genere?

Adesso è tutto più chiaro Magari aspettiamo Drago per una ulteriore soluzione!

[Drago96]

Ecco il topic di cui parlava Lasker: viewtopic.php?f=15&t=18547
C'è anche linkata una generalizzazione che si fa esattamente nello stesso modo...