OliForum Matematico

bestiedda ha scritto:

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-1 $ 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-1 $ modi in totale. Sbaglio

scusa il latex orrendo ma non riesco a fare le grafe

A dir la verità non ho capito molto, scusa

Comunque, il mio ragionamento valeva per $ n\ge 3 $ anche per come è stata costruita.
Per $ n=2 $ è abbastanza banale, ma si ricava in altro modo, saltando le cifre intermedie..

Comunque son un idiota. Sicuramente ho sbagliato la parte in cui calcolo gli m totali, perchè ci sono anche parecchie ripetizioni..

EUCLA ha scritto:Comunque son un idiota. Sicuramente ho sbagliato la parte in cui calcolo gli m totali, perchè ci sono anche parecchie ripetizioni..

capita a tutti di sbagliare lasciandosi sfuggire qualche particolare...ad esempio, prova a leggere la mia dimostrazione e fatti 2 risate

io cerco di calcolare direttamente gli $ $m $ con $ $MCD(m,6)>1 $ . Abbiamo visto che gli $ $m $ devono essere multipli di 2 e\o di 3. Per calcolare il numero di multipli di 2 vediamo che la prima cifra a destra può essere scelta in 2 modi (6 o 8 ) mentre le altre $ $n-1 $ cifre possono essere scelte in 4 modi diversi ciascuna. Dunque abbiamo in totale $ $2\cdot4^{n-1}=2^{2n-1} $ $ $m $ pari e un numero uguale di dispari. Ora dobbiamo scoprire quanti di questi dispari sono multipli di 3. A questo punto, consideriamo il numero formato dalle prime $ $n-1 $ cifre da destra: questo numero può essere scelto in $ $2\cdot4^{n-2}=2^{2n-3} $ modi diversi. Questo numero può essere congruo a 0,1,2 mod 3. Se è congruo a 1 o a 2 abbiamo solo una scelta possibile per l'ultima cifra, ovvero 8 e 1 rispettivamente. Se invece è congruo a 0, l'ultima cifra può essere sia 6 sia 9. A questo punto il problema è capire quanti di questi $ $2^{2n-3} $ numeri sono congrui rispettivamente a 0,1,2 mod 3.

A questo punto io ho pensato (sbagliando) che poichè tra le cifre da utilizzare 2 sono congrue a 0 mod 3, una è congrua a 1 e l'altra è congrua a 2, allora anche le congruenze mod 3 dei $ $2^{2n-3} $ numeri sono distribuite allo stesso modo, ovvero abbiamo $ $\frac{2^{2n-3}}{4} $ congrui a 1, $ $\frac{2^{2n-3}}{4} $ congrui a 2 e $ $\frac{2^{2n-3}}{2} $ congrui a 0, e in questo modo il numero totale di multipli di 3 dispari darebbe $ $2^{2n-4}\cdot 3 $ ma anche questo risultato risulta sbagliato

provo a dire come ho fatto io, fino ai numeri di 3 cifre.

l'idea che ho adottato è diversa dalle vostre: calcolare tutti i possibili numeri di n cifre avendo a disposizione le cifre dell'insieme dato S e sottraggo tutti i numeri che non sono nè multipli di 2, nè multipli di 3(avevo provato a calcolarli ma veniva più laborioso).

per n=1 è semplice, i numeri che soddisfano (m,6)>1 sono 3.
per n=2 calcolo tutti i possibili numeri di 2 cifre e poi sottraggo quelli che non ci servono.
sono 4^2=16 possibili numeri.
ora, scartando i numeri pari, devo considerare i numeri dispari non multipli di 3.
la cifra delle unità dovrà essere o 1 o 9.
con 1, posso scegliere in 3 modi la cifra delle decine, quindi ho 3 numeri.
con 9, devo considerare che la cifra delle decine non deve essere multipla di 3.
quindi in 2 modi(o 1 o 8 ). quindi 2 numeri.
la somma fa 5 numeri che non c'entrano niente.
sottraggo tale numero a 16 e ottengo 11 numeri che soddisfano il problema, per n=2.
per n=3 faccio la stessa cosa.
esculo i pari.
quindi distinguo due casi:
cifra unità 1
cifra unità 9
inizio con l'ultimo.
la somma delle altre due cifre non dovrà essere congrua a 0 modulo 3, quindi non dovrà essere multipla di 3.
quindi se come prima cifra(a partire da sinistra) scelgo 1, la seconda la potrò scegliere in 3 modi(1,6,9). solo che bisogna considerare anche la simmetria.
quindi, isolando il caso in cui la prima cifra sia uguale alla seconda(1,1) moltiplico gli altri due restanti modi per 2.
5 numeri.
se la prima cifra è 8, esistono altri 5 modi con cui posso accoppiarlo( 8,8 più altri due modi moltiplicati per due per simmetria).

se la cifra finale è 1.
se la prima cifra è 1, posso scegliere la seconda cifra in 3 modi, quindi 3 numeri.
il 6 e il nove in 2 modi, l'8 in un unico modo.
a questi aggiungo i tre numeri che hanno le stesse cifre(66,88,99).
quindi vengono 21 numeri che non sono nè multipli di 2 nè multipli di 3.
a questo punto sottraggo tale numero a 64 e viene 43 numeri.
adesso manca il caso n=4 e poi basta sommare i numeri trovati.

ho scoperto una regolarità che mi ha permesso di trovare una formula generale per trovare i numeri di n cifre che sono o multipli di $ 2 $ o multipli di $ 3 $ o multipli di $ 6 $.

dato un numero n, compreso strettamente tra $ 1 $ e $ 4 $, il numero di numeri di n cifre,che possiamo chiamare $ a_n $, che abbiano quelle proprietà è dato dalla formula seguente:

$ a_n=a_{n-1}+\frac{4^n}{2} $

dove $ a_0=1 $

adesso la dimostro:

date $ 4 $ cifre(quelle dell'insieme $ S $), i numeri di n cifre che si possono formare con quelle $ 4 $ cifre sono $ 4^n $
poichè tra quei $ 4 $ numeri, solo $ 2 $ sono pari, per formare i numeri pari di n cifre ho $ 2 $ modi soli per poter scegliere la cifra delle unità e per le altre cifre ho in tutto $ 4^{n-1} $ modi. poichè $ 2 $ è ovviamente la metà di quattro si ha:
$ 4^{n-1}\cdot\frac{4}{2}=\frac{4^n}{2} $.
così si è dimostrato che i numeri pari di n cifre sono esattamente la metà di tutti i possibili numeri.
poichè vogliamo sapere quanti numeri pari, multipli di tre e multipli di sei(pari multipli di tre) di $ n $ cifre ci sono, per dimostrare la tesi di partenza dobbiamo dimostrare che i multipli dispari di $ 3 $ di $ n $ cifre sono uguali a $ a_{n-1} $.
questa non sono ancora riuscito a dimostrarla bene. penso che si possa fare per induzione, però boh.
quindi, se non ho sbagliato i calcoli, i numeri di $ 4 $ cifre soddisfacenti le richieste del problema, sono $ 171 $.
poi si fa la somma di tutti i numeri trovati.

ho avuto un'idea....e speriamo che sia la volta buona.

chiamiamo $ $x_n $ i numeri $ $x $ di $ $n $ cifre scelte in $ $S=\{1,6,8,9\} $ :ho $ $4^n $ numeri $ $x_n $: $ $a_n $ di questi sono $ $\equiv1(mod3) $ , $ $b_n $ di questi sono $ $\equiv2(mod3) $ , $ $c_n $ di questi sono $ $\equiv0(mod3) $ . Ovviamente $ $a_n+b_n+c_n=4^n $ . Ora io voglio trovare gli $ $a_{n+1},b_{n+1},c_{n+1} $ , ovvero il numero di $ $x_{n+1} $ rispettivamente congrui a 1, a 2 e a 0 mod 3. Per conoscere $ $a_{n+1} $ , consideriamo in quanti modi si può costruire un numero $ $x_{n+1}\equiv1(mod3) $ a partire dalle prime $ $n $ cifre da destra, ovvero a partire da tutti gli $ $x_n $: se $ $x_n \equiv 1(mod3) $ abbiamo 2 possibilità (6 e 9) per scegliere l'ultima cifra, se $ $x_n \equiv 2(mod3) $ abbiamo 1 possibilità (8 ) per scegliere l'ultima cifra , se $ $x_n \equiv 0(mod3) $ abbiamo 1 possibilità (1) per scegliere l'ultima cifra. Dunque $ $a_{n+1}=2a_n+b_n+c_n $. Ripetendo le stesse considerazioni per $ $b_{n+1} $ e $ $c_{n+1} $ avremo che $ $b_{n+1}=a_n+2b_n+c_n $ e $ $c_{n+1}=a_n+b_n+2c_n $ .

Ora mi interessa dimostrare che $ $a_n=b_n $ : verifichiamo innanzitutto che $ $a_1=b_1 $ e questo è ovvio sono entrambi uguali a 1. Ora consideriamo l'uguaglianza $ $a_{n+1}=2a_n+b_n+c_n $ : sottraiamo ad entrambi i membri $ $b_{n+1} $ e otteniamo che $ $a_{n+1}-b_{n+1}=a_n-b_n $ ; noi sappiamo che la prima coppia $ $a_1-b_1=0 $ , dunque per ogni $ $n>1 $ $ $a_n-b_n=0 $ , ovvero $ $a_n=b_n $.

Ora dimostriamo che $ $c_n-a_n=1 $ . Partendo dall'uguaglianza $ $c_{n+1}=a_n+b_n+2c_n $ , sottraiamo da entrambi i membri $ $a_{n+1} $ e otteniamo che $ $c_{n+1}-a_{n+1}=c_n-a_n $, ma poichè $ $c_1-a_1=1 $ , allora per ogni $ $n>1 $ $ $c_n-a_n=1 $

Ora scriviamo $ $4^n $ in funzione del numero di multipli di 3 tra tutti gli $ $x_n $ , ovvero $ $c_n $ : $ $4^n=a_n+b_n+c_n=(c_n-1)+(c_n-1)+c_n=3c_n-2 $ : il numero dei multipli di 3 in funzione di $ $n $ è quindi $ $c_n=\frac{4^n+2}{3} $ . Sappiamo che esattamente la metà di questi multipli di 3 sono pari, per cui avremo che il numero di dispari multipli di 3 è esattamente $ $\frac{4^n+2}{6} $ . Sommato al numero totale di numeri pari, cioè $ $\frac{4^n}{2} $ , avremo che $ $m=\frac{4^n+2}{6}+\frac{4^n}{2}=\frac{4^{n+1}+2}{6} $

prendete con le pinze il risultato, devo ancora rivedere bene quello che ho fatto!

se qualche folle ha voglia di leggere questo malloppo, mi può dire se è giusto? grazie

potete dirmi se anche il mio è giusto?

matteo16 ha scritto:poichè vogliamo sapere quanti numeri pari, multipli di tre e multipli di sei(pari multipli di tre) di $ n $ cifre ci sono, per dimostrare la tesi di partenza dobbiamo dimostrare che i multipli dispari di $ 3 $ di $ n $ cifre sono uguali a $ a_{n-1} $.
questa non sono ancora riuscito a dimostrarla bene. penso che si possa fare per induzione, però boh.

l'idea è giusto, pero dimostrarlo?

@bestiedda: è la stessa soluzione che mi è arrivata da yahoo ( in realtà chi mi ha risposto è 3C273, una forumista che per mp mi ha fornito una soluzione ancora piu elementare, semplicemente cambiando base; chi vuole trovala?..)