OliForum Matematico

Quanti termini ha il polinomio che si ottiene sviuppando $ (x^7 + x^3 + 1)^{1000} $ e sommando i termini simili ?


Soluzione $ 6986 $

Dovresti specificare da dov'è tratta (Quinta disfida matematica Urbi et Orbi) comunque é un problema carino che non sono riuscito a risolvere durante quella gara , e dato che non penso che il professor Callegari non farà la video soluzione di questo esercizio (ma che piuttosto tratterà qualcuno come il 20) mi piacerebbe sapere se qualcuno ha un metodo di risoluzione carino per questo problema

$(x^7+x^3+1)^{1000}$ è un polinomio di grado $7000$, perciò può essere formato al massimo da $7001$ termini non simili.
Ma $(x^7+x^3+1)^{1000}=\underbrace{(x^7+x^3+1)(x^7+x^3+1)(x^7+x^3+1)(x^7+x^3+1) \cdots (x^7+x^3+1)}_{1000}$ e quindi per qualsiasi $c=7a+3b$, con $a,b$ non negativi e $a+b \le 1000$, $x^c$ è simile a un termine di $(x^7+x^3+1)^{1000}$; infatti $x^c$ è ottenibile moltiplicando tra loro i termini della sequenza formata da $a \quad x^7$, $b \quad x^3 $ e $1000-a-b \quad 1$, scelti da ognuno dei $1000$ fattori.

Bisogna dunque trovare il numero di termini $c$ rappresentabili come $7a+3b$, nel rispetto delle condizioni di cui sopra.

La generica equazione diofantea $7a+3b=c$ ha soluzioni $a=c-3k,b=-2c+7k$ e le condizioni sono:
$$\left\{ \begin{array}{l}
a \ge 0\\
b \ge 0\\
a+b \le 1000\\
\end{array} \right.
\Rightarrow
\left\{ \begin{array}{l}
k \le \frac{c}{3}\\
k \ge \frac{2}{7}c\\
k \le 250 + \frac{c}{4}\\
\end{array} \right. \Rightarrow
\begin{cases}
\frac{2}{7}c \le k \le \frac{1}{3}c& \text{se $0 \le c < 3000$}\\
\frac{2}{7}c \le k \le250 + \frac{1}{4}c& \text{se $3000 \le c \le 7000$}\\
\end{cases}
$$
Il problema si riduce quindi a trovare per quali valori di $0 \le c < 3000 \ \exists k \ \text{intero} : k \in \left[\frac{2}{7}c,\frac{1}{3}c\right]$ e per quali valori di $3000 \le c \le 7000 \ \exists k \ \text{intero} : k \in \left[\frac{2}{7}c,250+\frac{1}{4}c\right]$.
Per tutti i valori di $21 \le c \le 6972$ le condizioni sono soddisfatte; quanto agli altri, si verifica direttamente che gli unici valori di $c$ che non soddisfano le condizioni sono $1,2,4,5,8,11,6983,6987,6990,6991,6994,6995,6997,6998,6999$, quindi i termini non simili di $(x^7+x^3+1)^{1000}$ sono $7001-15=6986$

santilli ha scritto: [...] un metodo di risoluzione carino per questo problema

Scusate, la mia è una soluzione alquanto brutta...

Nemo , la tua soluzione è molto bella, non dire così xD anzi , grazie mille perché è uno dei problemi in cui la mia squadra ogni tanto si blocca e vedere un metodo efficace scritto è davvero un grande aiuto! Grazie Nemo ^.^ (magari 1-2 centinaia di punti in futuro della mia squadra saranno merito tuo ^.^)

santilli ha scritto:Dovresti specificare da dov'è tratta (Quinta disfida matematica Urbi et Orbi)

Beh non è un dogma, suvvia.

xD é vero che non é un dogma xD ma so che il (sommo) prof. Callegari cerca sempre i link a quesiti del forum che riguardano questa gara , quindi specificare mi sembrava carino nei suoi confronti ^.^ (non volevo fucilare LorMath xD)