Dal momento che non trovo online una dimostrazione, ma solo il risultato numerico, chiedo aiuto a voi per questo esercizio (cesenatico semifinale a squadre):
Per sconfiggere le astronavi aliene, è necessario determinare tutti i numeri interi positivi tali che sono uguali a 245
volte la somma delle loro cifre scritti in base 7. Quanto vale la somma di questi numeri (scritta in base 10)?
La risposta è 4410 e riesco a trovare i suddetti numeri solo a tentativi, ma non a fare qualcosa di più "serio". Sono bloccato qui :
Sia S(x) la somma delle cifre di x in base 7, allora devo trovare tutti gli interi N = 245 * S(N) dunque N=245*k e semplificando ottengo che k = S(245k) quindi k = S(5k) (ho semplificato il 7^2 che rimaneva poiché aggiunge solo 2 zeri alla fine), e qui non riesco a procedere se non a tentativi.
Esercizio 2 gara a squadre 2015
-
carlotheboss
- Messaggi: 10
- Iscritto il: 01 apr 2015, 18:32
- Località: Bergamo
Re: Esercizio 2 gara a squadre 2015
Un approccio standard a questo tipo di problemi è quello di trovare un bound al numero di cifre che può avere $n$, e poi fare i casi.
In questo problema, ad esempio, sia $k$ il numero di cifre di $n$ (in base $7$). Allora, il minimo valore possibile per $n$ è $7^{k - 1}$ ma, d'altra parte, la somma delle cifre non può superare $6k$, dunque $n = 245S(n) \le 245 \cdot 6k$. Mettendo insieme queste due disuguaglianze, troviamo che $$7^{k - 1} \le n \le 245 \cdot 6k \Rightarrow 7^{k - 3} \le 30k$$
che si risolve per $k \le 5$ (per induzione, se proprio vogliamo formalizzare, ma tanto è una GaS
).
E a questo punto non resta che fare i casi, mi sembra che ci siano solo 3 soluzioni.
In questo problema, ad esempio, sia $k$ il numero di cifre di $n$ (in base $7$). Allora, il minimo valore possibile per $n$ è $7^{k - 1}$ ma, d'altra parte, la somma delle cifre non può superare $6k$, dunque $n = 245S(n) \le 245 \cdot 6k$. Mettendo insieme queste due disuguaglianze, troviamo che $$7^{k - 1} \le n \le 245 \cdot 6k \Rightarrow 7^{k - 3} \le 30k$$
che si risolve per $k \le 5$ (per induzione, se proprio vogliamo formalizzare, ma tanto è una GaS
).E a questo punto non resta che fare i casi, mi sembra che ci siano solo 3 soluzioni.
-
carlotheboss
- Messaggi: 10
- Iscritto il: 01 apr 2015, 18:32
- Località: Bergamo
Re: Esercizio 2 gara a squadre 2015
grazie mille cip999 
Ultima cosa: non sono ancora un po' tantini i casi con k>=5? perché o imposto io il problema in maniera lunga e stupida o boh, facendo N = 245 * x, tutti gli x < 69 danno un numero con k<=5 cifre in base 7... o serve qualche altra osservazione intelligente per ridurre i casi o serve proprio un altro metodo ...
Ultima cosa: non sono ancora un po' tantini i casi con k>=5? perché o imposto io il problema in maniera lunga e stupida o boh, facendo N = 245 * x, tutti gli x < 69 danno un numero con k<=5 cifre in base 7... o serve qualche altra osservazione intelligente per ridurre i casi o serve proprio un altro metodo ...
Re: Esercizio 2 gara a squadre 2015
Beh, un metodo che funziona (almeno in questo caso) è scrivere $n$ in forma polinomiale (insomma, la somma delle cifre moltiplicate per l'opportuna potenza di $7$). Ad esempio, per $k = 1$, ho che $n$ ha una sola cifra (diciamo $a$) e dunque devo avere $$a = 245a$$ che ha come unica soluzione $0$, che ovviamente non è accettabile (almeno una cifra diversa da $0$ la devo avere 
).
Per $k = 2$, devo risolvere $$7a + b = 245(a + b) \Rightarrow 238a + 244b = 0$$ e anche qui non ci sono soluzioni.
Vado avanti, $k = 3$, quindi $$49a + 7b + c = 245(a + b + c) \Rightarrow 196a + 238b + 244c = 0$$
e, come prima, niente soluzioni.
Per $k = 4$ devo avere $$343a + 49b + 7c + d = 245(a + b + c) \Rightarrow 98a - 196b - 238c - 244d = 0$$ Ora, notiamo che $98$, $196$ e $238$ sono tutti divisibili per $7$, mentre $244$ non lo è, quindi si deve necessariamente avere $d = 0$. Sostituendo e semplificando un fattore $7$, otteniamo $$14a - 28b - 34c = 0$$. Di nuovo, $7 \mid 14, \: 28$ ma $7 \nmid 34$, da cui $c = 0$ e quindi (sostituendo e semplificando il possibile) $$a - 2b = 0$$ e qui è semplice trovare le soluzioni, che sono le coppie $(a,b)$ per cui $a = 2b$, e dunque $(2,1)$, $(4,2)$ e $(6,3)$. Queste corrispondono ai numeri (in base $7$, ovviamente) $2100$, $4200$ e $6300$.
Lascio a te il caso $k = 5$, anticipandoti però che non ci sono soluzioni.
).Per $k = 2$, devo risolvere $$7a + b = 245(a + b) \Rightarrow 238a + 244b = 0$$ e anche qui non ci sono soluzioni.
Vado avanti, $k = 3$, quindi $$49a + 7b + c = 245(a + b + c) \Rightarrow 196a + 238b + 244c = 0$$
e, come prima, niente soluzioni.
Per $k = 4$ devo avere $$343a + 49b + 7c + d = 245(a + b + c) \Rightarrow 98a - 196b - 238c - 244d = 0$$ Ora, notiamo che $98$, $196$ e $238$ sono tutti divisibili per $7$, mentre $244$ non lo è, quindi si deve necessariamente avere $d = 0$. Sostituendo e semplificando un fattore $7$, otteniamo $$14a - 28b - 34c = 0$$. Di nuovo, $7 \mid 14, \: 28$ ma $7 \nmid 34$, da cui $c = 0$ e quindi (sostituendo e semplificando il possibile) $$a - 2b = 0$$ e qui è semplice trovare le soluzioni, che sono le coppie $(a,b)$ per cui $a = 2b$, e dunque $(2,1)$, $(4,2)$ e $(6,3)$. Queste corrispondono ai numeri (in base $7$, ovviamente) $2100$, $4200$ e $6300$.
Lascio a te il caso $k = 5$, anticipandoti però che non ci sono soluzioni.