Esercizio 2 gara a squadre 2015

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
cip999
Messaggi: 153
Iscritto il: 26 nov 2013, 14:44

Re: Esercizio 2 gara a squadre 2015

Messaggio da cip999 »

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 :lol: ).
E a questo punto non resta che fare i casi, mi sembra che ci siano solo 3 soluzioni.
cip999
Messaggi: 153
Iscritto il: 26 nov 2013, 14:44

Re: Esercizio 2 gara a squadre 2015

Messaggio da cip999 »

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. :)
Rispondi