OliForum Matematico

Determinare quanti interi della $ 100^a $ riga del triangolo di Tartaglia-Pascal non sono divisibili da 3 (la $ 100^a $ riga è quella che inizia con 1, 100, ... ).

A me sembra piuttosto teoria dei numeri, ma vabbè... Si tratta di determinare il numero n dei coefficienti binomiali $ \displaystyle b_k = \binom{100}{k} $, con $ k = 0, 1, \ldots, 50 $, per cui $ v_k := v_3(b_k) = 0 $, dove $ v_3(\cdot) $ denota una valutazione 3-adica. Per via dell'identità di Legendre-De Polignac: $ \displaystyle v_k = 48 - s_k = 0 $ sse $ s_k = 48 $, dove $ \displaystyle s_k := \sum_{i=1}^3 \left\lfloor \frac{k}{3^i}\right\rfloor + \sum_{i=1}^4 \left\lfloor \frac{100-k}{3^i} \right\rfloor $. Se $ k = 3q_k + r_k = 9p_k + t_k $, con $ 0 \le r_k < 3 $ e $ 0 \le t_k < 9 $, allora $ \displaystyle s_k = 48 + \left\lfloor \frac{1- r_k}{3}\right \rfloor + \left\lfloor \frac{1- t_k}{9}\right \rfloor +\rho_k $, dove $ \displaystyle \rho_k := \left\lfloor \frac{k}{27}\right\rfloor + \left\lfloor \frac{19-k}{27} \right\rfloor + \left\lfloor \frac{19-k}{81} \right\rfloor $. Perciò $ s_k < 48 $, a meno che $ k \equiv \{0, 1\} \bmod 9 $ e $ \rho_k = 0 $. Senonché $ \rho_k < 0 $, se $ 19 < k \le 50 $. Restano da esaminare i casi $ k = 0, k = 1, k = 9, k = 10, k = 18\mbox{ e }k = 19 $. In ciascuno di questi, si trova effettivamente $ s_k = 48 $. Da qui n = 6, per concluderne che 12 è la risposta al quesito proposto.

Non ho capito bene il procedimento di Hit, ma dovrebbe venire 12 (per sicurezza e visto che non trovo l'errore nei passaggi precedenti ho controllato a posteriori col PC).

Siccome si può fare in maniera molto elementare, non scrivo i dettagli ma solo uno sketch:

1. è facile capire che forma ha la riga 81 del triangolo se vista modulo 3

2. usando la proprietà fondamentale del triangolo, dedurre la riga 90 è facile e la 99 appena delicato (sempre modulo 3)

3. si deducono le congruenze modulo 3 della riga 100 e si ha finito.

E' semplice, non c'è nessun errore: ho dimenticato i casi k = 0 e k = 1. La risposta pertanto è effettivamente 12.

Possiamo calcolare il numero dei coefficienti non divisibili da 3 considerando i coefficienti dello sviluppo del polinomio $ (1+x)^{100} $ modulo 3.
$ (1+x)^3\equiv1+x^3 $ (mod 3) e anche $ (1+x)^{3k}\equiv 1+x^{3k} $ (mod 3). Si ha $ 100=81+2\cdot9+1 $,
quindi $ (1+x)^{100}\equiv (1+x^{81})(1+2x^9+x^{18})(1+x) $ (mod 3)
Nell'ultimo prodotto $ 2\cdot3\cdot2=12 $ potenze sono diverse (perchè ogni intero può essere scritto in base 3 in modo unico) e i coefficienti sono tutti diversi da 0 modulo 3. Allora la risposta è 12.

Il problema si poteva risolvere immediatamente utilizzando un risultato dovuto a Gauss:
Se n è scritto cone $ a_ka_{k-1}\ldots a_0 $ in base p (p primo) allora nella riga n del triangolo di Tartaglia-Pascal ci sono $ (a_k+1)(a_{k-1}+1)\cdots(a_0+1) $ coefficienti non divisibili da p. Si può dimostrare ragionando come nel caso particolare del problema.

Comunque il triangolo di Partaglia-Pascal non è stato inventato ne dall'uno ne dall'altro, ma dal matematico cinese Zhou Jije nel 1303.