il forum ufficiale delle olimpiadi della matematica
https://www.oliforum.it/
)ma le cifre possono anche ripetersi o no? tipo 99 oppure 9999 ecc.?jordan ha scritto:Quanti sono gli interi positivi $ m $ tali che hanno esattamente $ n $ cifre, e tutte le sue cifre sono nell'insieme $ S=\{1,6,8,9\} $ e risulta $ MCD(m,6)>1 $?
(Quasi quasi sembra da febbraio
)poichè MCD(m,6)>1 dobbiamo avere che m deve essere pari e\o multiplo di 3. Perchè m sia pari l'ultima cifra può essere scelta solo in 2 modi (6 o 8 ) e tutte le altre cifre possono essere scelte in 4 modi. Dunque abbiamo esattamente 2*4^{n-1}=2^{2n-1} pari e altrettanti dispari. Resta da stabilire quanti di questi dispari sono multipli di 3, e mò sò c***i...ho provato anche a scrivere un pò di valori di m con n fissato ma non trovo nessuna regolarità
è quello che blocca anche me.bestiedda ha scritto:dunque...spoilero perchè il mio è solo un abbozzo di soluzione
poichè MCD(m,6)>1 dobbiamo avere che m deve essere pari e\o multiplo di 3. Perchè m sia pari l'ultima cifra può essere scelta solo in 2 modi (6 o 8 ) e tutte le altre cifre possono essere scelte in 4 modi. Dunque abbiamo esattamente 2*4^{n-1}=2^{2n-1} pari e altrettanti dispari. Resta da stabilire quanti di questi dispari sono multipli di 3, e mò sò c***i...ho provato anche a scrivere un pò di valori di m con n fissato ma non trovo nessuna regolarità
hintino??
caspitaEUCLA ha scritto:Hint 1:
----------------------------------------------------------------------------------
Quanti sono i numeri di n cifre, scelte tra quelle dell'insieme? Sono A
-----------------------------------------------------------------------------------
Hint 2:
---------------------------------------------------------------------------------
Provo a contare quanti sono i numeri tali che mcd(n,6)=1. Sono B
--------------------------------------------------------------------------------
Hint 3 (è la soluzione):
-----------------------------------------------------------------------
Per contare B, fisso l'ultima cifra a destra. Quante cifre ci possono stare?
Ora scelgo a caso in S, n-2 cifre.
Mi rimane la cifra a sinistra da fissare. Vedo la congruenza modulo 3 della somma delle cifre del numero fino a ora ottenuto, di conseguenza, la cifra che manca può essere solo in un certo modo, sommando i risultati che mi danno i vari casi, ottengo quanti sono i B.
Il risultato ora è N-B.
-----------------------------------------------------------------------
Risultato spero giusto:
---------------
2^{2n-1}
--------------
Il ragionamento dovrebbe esser giusto, al limite può essere che abbia sbagliato il risultato, quindi siete invitati a controllare
io avevo fatto in un modo molto più laborioso che magari dopo posto.Faccio il guastafesteEUCLA ha scritto: Vedo la congruenza modulo 3 della somma delle cifre del numero fino a ora ottenuto, di conseguenza, la cifra che manca può essere solo in un certo modo
EDIT:anche io avevo pensato ad una soluzione simile alla tua (che si basasse sulle congruenze mod 3 delle prime n-1 cifre da destra) ma non sono riuscito a capire come si distribuiscono i residui mod 3 in tutti gli $ $m $di $ $n $cifre possibili. Mi potresti spiegare meglio quel passaggio? Se lo ritieni opportuno puoi rispondermi in mp
mi ha preceduto TBPL: se il numero ottenuto è congruo a 1 si può scegliere solo 8, se è congruo a 2 si può scegliere solo 1 ma se è congruo a 0 si può scegliere 6 o 9. Quanti sono questi numeri?
Onore alla pazienzabestiedda ha scritto:@EUCLA: non credo che il risultato sia giusto, ho scritto tutti gli $ $m $di 3 cifre e mi vengono 43 $ $m $"buoni", mentre per il tuo risultato dovrebbero essere 32
. Mi fido del tuo risultato, ci sarà qualcosa di sbagliato nel mio ragionamento, sinceramente non ho voglia di controllare anche io 43 casi quindi dici che 2^{2n-1} è il numero dei numeri di n cifre che soddisfano le richieste giusto(se non ho capito male)?EUCLA ha scritto:No, "solo in un certo modo" non voleva dire che c'è solo un modo, semplicemente
che ci sono delle cose da escludere.
Arrivo a quel punto e ho già $ 4^{n-2} $ combinazioni.
Somma delle cifre congrua a 0 mod 3 → 1,8 [2]
Somma delle cifre congrua a 1 mod 3 → 1,6,9 [3]
Somma delle cifre congrua a 2 mod 3 → 6,8,9 [3]
Quelli indicati a destra sono ovviamente quelli che posso scegliere ancora.
Il risultato allora sarà $ 4^{n-2}\cdot 2 +4^{n-2}\cdot 3+4^{n-2}\cdot 3 =4^{n-2}(2+3+3)=2^{2n-4}\cdot 2^3=2^{2n-1} $
in questo modo tu stai considerando come se ci fossero $ $4^n-2 $ modi per scegliere $ $n-1 $ cifre tali che la loro somma è congrua a 0 mod 3, altrettanti in modo che la somma è congrua ad 1 ed altrettanti in modo che la somma è congrua a 2, mentre in realtà sono $ $4^n-2 $ modi in totale. SbaglioEUCLA ha scritto:No, "solo in un certo modo" non voleva dire che c'è solo un modo, semplicemente
che ci sono delle cose da escludere.
Arrivo a quel punto e ho già $ 4^{n-2} $ combinazioni.
Somma delle cifre congrua a 0 mod 3 → 1,8 [2]
Somma delle cifre congrua a 1 mod 3 → 1,6,9 [3]
Somma delle cifre congrua a 2 mod 3 → 6,8,9 [3]
Quelli indicati a destra sono ovviamente quelli che posso scegliere ancora.
Il risultato allora sarà $ 4^{n-2}\cdot 2 +4^{n-2}\cdot 3+4^{n-2}\cdot 3 =4^{n-2}(2+3+3)=2^{2n-4}\cdot 2^3=2^{2n-1} $
ho controllato perchè avevo impostato la soluzione e mi dava giusto per $ $n=2 $ e per $ $n=3 $ mi dava 44 mentre il risultato giusto era 43EUCLA ha scritto:Onore alla pazienza
magari poi la posto così cerchiamo di correggerla dato che ci sono andato vicino