Problema 79 del OneHoundredProblems2025

[EmilioC7]

Un anno fa mi sono imbattuto in questo problema durante una gara senza riuscire a risolverlo, mi domandavo se qualcuno avesse idee su come farlo.
Denotiamo con [x] il più grande intero <=x. Per ogni intero positivo n, definiamo f(n) semplicemente come il resto della divisione di n per 2, ovvero f(n)=1 se n è dispari, f(n)=0 se pari. Dire quanto vale la quantità:
f([1/45])+f([21/45])+f([321/45])+...+f([10987654321/45])+f([1110987654321/45])+...+f([99989796...54321/45]).

(P.S. La soluzione è 44, ma anche conoscendola capire come arrivarci non è semplice...).

[Sebastiano Marchi]

Propongo la mia soluzione.

Testo nascosto:

Di fatto ci interessa quanti di questi numeri, divisi per 45, abbiano parte intera pari. Diciamo questo numero n, il risultato sarà 99-n.
Diciamo k il numero diviso 45, k deve essere tale che, per un qualche t naturale, [math]2t\leq k < 2t+1. Portando il 45 al di fuori, [math]90t\leq m < 90t+45. Portando il 90 dentro, [math]t\leq \frac{m}{90}<t+\frac{1}{2}, abbiamo quindi che, dividendo per 90 il numero m, la parte dopo la virgola deve essere tra 0 e 0.5, non al di fuori. Detto r il resto di m dividendo per 90, è come dire [math]\frac{1}{2}>\frac{r}{90}, ossia [math]r< 45. Ci interessa quindi il valore di m modulo 90, sappiamo che il numero è congruente a 1 modulo 2, che è congruente a 1 modulo 5. Ci interessa a cosa è congruente mod 9 per poter applicare il teorema cinese del resto e risolvere il problema. Per farlo si sfrutta il fatto che la somma delle cifre di m è uguale modulo 9 alla somma dei numeri da 1 a m', dove m' è al massimo 99, e che questa somma di cifre è proprio uguale a m modulo 9. La somma delle cifre è [math]\frac{m'(m'+1)}{2}. Il teorema del resto ci dà questo valore: [math]r\equiv1\times 45\times1+1\times18\times2+\frac{m'(m'+1)}{2}\times10\times1 mod 90. Si ottiene [math]r\equiv 81+10\frac{m'(m'+1)}{2} mod [math]90. A noi però non interessa un generico valore modulo 90, ma il resto nella divisione per 90. Pertanto dobbiamo sostituire [math]\frac{m'(m'+1)}{2} con un qualsiasi valore equivalente modulo 9, in modo da ottenere un valore tra 0 e 89 per r. Ora bisogna capire quali valori può ottenere [math]\frac{m'(m'+1)}{2} al variare di m' e conseguentemente per quali valori di m' r è effettivamente minore di 45. Abbiamo [math](0\to0),(1\to 1),(2\to3),(3\to6),(4\to1),(5\to6),(6\to3),(7\to1),(8\to0), dove la freccia manda il valore di m' modulo 9 al valore di [math]\frac{m'(m'+1)}{2}, sempre modulo 9. Facciamo lo stesso mandando dal valore di [math]\frac{m'(m'+1)}{2} modulo 9 al valore di r: [math](0\to81),(1\to1),(3\to21),(6\to51). Pertanto rimangono come valori modulo 9 di m' solo [math](1,2,4,6,7), ossia 5 su 9. Pertanto, siccome m' va da 1 a 99, e 99 è divisibile per 9, il numero di numeri che darà un numero pari è [math]\frac{5}{9} di 99 e pertanto quelli che daranno un numero dispari sono i [math]\frac{4}{9}, ossia 44, che è la soluzione.

[EmilioC7]

Grande! Grazie mille ✌

[davidsolano]

Secondo me la chiave è osservare la parità di ⌊k/45⌋ invece di cercare di calcolare ogni termine. Dal momento che f(n) dipende solo dal fatto che il quoziente sia pari o dispari, conviene studiare come variano i blocchi consecutivi di numeri quando si divide per 45. In pratica, ogni 45 numeri la parte intera aumenta di 1, quindi la parità si alterna regolarmente.

Per le sequenze “crescenti” del tipo 1, 21, 321, 10987654321 ecc. credo che il trucco sia contare quante volte si cade in un intervallo che dà quoziente dispari, senza entrare nel dettaglio di ogni singolo valore. Una volta vista questa periodicità, il risultato 44 diventa più plausibile, anche se ammetto che non è immediato arrivarci al primo colpo.