Sommatoria in binario

XXI Gara Nazionale a Squadre – Finale nazionale 17 settembre 2020 – Numero 19

«Solo un atto di vero amore può sciogliere un cuore di ghiaccio». Invece, per un cervello di ghiaccio un rimedio efficace potrebbe essere cimentarsi con il seguente problema.

Siano $z(n)$ e $u(n)$ due funzioni che restituiscono rispettivamente il numero di zeri e di uni nella scrittura in base 2 del numero $n$ , e sia $\displaystyle f(n)=\frac{(-1)^{z(n)}}{2^{u(n)}}$ .
Per esempio, quindi, $\displaystyle f(13)=f(1101_2)=\frac{(-1)^1}{2^3} = -\frac{1}{8}$ , mentre $\displaystyle f(17)=f(10001_2)=\frac{(-1)^3}{2^2}=-\frac{1}{4}$ .
Calcolare quanto vale la somma $f(1)+f(2)+f(3)+...+f(1023)$ .

Rispondere con la somma di numeratore e denominatore della frazione ridotta ai minimi termini.

Soluzione 1

Forza bruta: calcolo i valori di $f(n)$ per ogni $n$ da 1 a 1023

$n_{10}$	$n_{2}$	$z(n)$	$u(n)$	$f(n)$	Totale
1	1	0	1	$\displaystyle \frac{1}{2}$	$\displaystyle \frac{1}{2}$
2	10	1	1	$\displaystyle -\frac{1}{2}$	0
3	11	0	2	$\displaystyle \frac{1}{4}$	$\displaystyle \frac{1}{4}$
4	100	2	1	$\displaystyle \frac{1}{2}$	$\displaystyle \frac{3}{4}$
5	101	1	2	$\displaystyle -\frac{1}{4}$	$\displaystyle \frac{1}{2}$
…	…	…	…	…	…
13	1101	1	3	$\displaystyle -\frac{1}{8}$	$\displaystyle \frac{3}{8}$
…	…	…	…	…	…
17	10001	3	2	$\displaystyle -\frac{1}{4}$	$\displaystyle \frac{9}{16}$
…	…	…	…	…	…
1022	1111111110	1	9	$\displaystyle -\frac{1}{512}$	$\displaystyle \frac{85}{256}$
1023	1111111111	0	10	$\displaystyle \frac{1}{1024}$	$\displaystyle \frac{341}{1024}$

Osserva

Ho compilato la tabella utilizzando Python!
La risposta al quesito: 341+1024 = 1365
Non si intravede uno schema risolutivo semplice.

Soluzione 2

Faccio i conteggi raggruppando per numero di 1 nella rappresentazione binaria (i valori della funzione hanno lo stesso denominatore)

$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
1	0	1	1	$\displaystyle \frac{1}{2}$	$\displaystyle \frac{1}{2}$
1	1	10	1	$\displaystyle -\frac{1}{2}$	$\displaystyle -\frac{1}{2}$
1	2	100	1	$\displaystyle \frac{1}{2}$	$\displaystyle \frac{1}{2}$
1	3	1000	1	$\displaystyle -\frac{1}{2}$	$\displaystyle -\frac{1}{2}$
1	4	10000	1	$\displaystyle \frac{1}{2}$	$\displaystyle \frac{1}{2}$
1	5	100000	1	$\displaystyle -\frac{1}{2}$	$\displaystyle -\frac{1}{2}$
1	6	1000000	1	$\displaystyle \frac{1}{2}$	$\displaystyle \frac{1}{2}$
1	7	10000000	1	$\displaystyle -\frac{1}{2}$	$\displaystyle -\frac{1}{2}$
1	8	100000000	1	$\displaystyle \frac{1}{2}$	$\displaystyle \frac{1}{2}$
1	9	1000000000	1	$\displaystyle -\frac{1}{2}$	$\displaystyle -\frac{1}{2}$	0
$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
2	0	11	1	$\displaystyle \frac{1}{4}$	$\displaystyle \frac{1}{4}$
2	1	110 101	$\displaystyle {2 \choose 1}=2$	$\displaystyle -\frac{1}{4}$	$\displaystyle -\frac{2}{4}$
2	2	1100 … 1001	$\displaystyle {3 \choose 2}=3$	$\displaystyle \frac{1}{4}$	$\displaystyle \frac{3}{4}$
2	3	11000 … 10001	$\displaystyle {4 \choose 3}=4$	$\displaystyle -\frac{1}{4}$	$\displaystyle -\frac{4}{4}$
2	4	110000 … 100001	$\displaystyle {5 \choose 4}=5$	$\displaystyle \frac{1}{4}$	$\displaystyle \frac{5}{4}$
2	5	1100000 … 1000001	$\displaystyle {6 \choose 5}=6$	$\displaystyle -\frac{1}{4}$	$\displaystyle -\frac{6}{4}$
2	6	11000000 … 10000001	$\displaystyle {7 \choose 6}=7$	$\displaystyle \frac{1}{4}$	$\displaystyle \frac{7}{4}$
2	7	110000000 … 100000001	$\displaystyle {8 \choose 7}=8$	$\displaystyle -\frac{1}{4}$	$\displaystyle -\frac{8}{4}$
2	8	1100000000 … 1000000001	$\displaystyle {9 \choose 8}=9$	$\displaystyle \frac{1}{4}$	$\displaystyle \frac{9}{4}$	$\displaystyle \frac{5}{4}$
$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
3	0	111	1	$\displaystyle \frac{1}{8}$	$\displaystyle \frac{1}{8}$
3	1	1110 … 1011	$\displaystyle {3 \choose 1}=3$	$\displaystyle -\frac{1}{8}$	$\displaystyle -\frac{3}{8}$
3	2	11100 … 10011	$\displaystyle {4 \choose 2}=6$	$\displaystyle \frac{1}{8}$	$\displaystyle \frac{6}{8}$
3	3	111000 … 100011	$\displaystyle {5 \choose 3}=10$	$\displaystyle -\frac{1}{8}$	$\displaystyle -\frac{10}{8}$
3	4	1110000 … 1000011	$\displaystyle {6 \choose 4}=15$	$\displaystyle \frac{1}{8}$	$\displaystyle \frac{15}{8}$
3	5	11100000 … 10000011	$\displaystyle {7 \choose 5}=21$	$\displaystyle -\frac{1}{8}$	$\displaystyle -\frac{21}{8}$
3	6	111000000 … 100000011	$\displaystyle {8 \choose 6}=28$	$\displaystyle \frac{1}{8}$	$\displaystyle \frac{28}{8}$
3	7	1110000000 … 1000000011	$\displaystyle {9 \choose 7}=36$	$\displaystyle -\frac{1}{8}$	$\displaystyle -\frac{36}{8}$	$\displaystyle -\frac{20}{8}$
$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
4	0	1111	1	$\displaystyle \frac{1}{16}$	$\displaystyle \frac{1}{16}$
4	1	11110 … 10111	$\displaystyle {4 \choose 1}=4$	$\displaystyle -\frac{1}{16}$	$\displaystyle -\frac{4}{16}$
4	2	111100 … 100111	$\displaystyle {5 \choose 2}=10$	$\displaystyle \frac{1}{16}$	$\displaystyle \frac{10}{16}$
4	3	1111000 … 1000111	$\displaystyle {6 \choose 3}=20$	$\displaystyle -\frac{1}{16}$	$\displaystyle -\frac{20}{16}$
4	4	11110000 … 10000111	$\displaystyle {7 \choose 4}=35$	$\displaystyle \frac{1}{16}$	$\displaystyle \frac{35}{16}$
4	5	111100000 … 100000111	$\displaystyle {8 \choose 5}=56$	$\displaystyle -\frac{1}{16}$	$\displaystyle -\frac{56}{16}$
4	6	1111000000 … 1000000111	$\displaystyle {9 \choose 6}=84$	$\displaystyle \frac{1}{16}$	$\displaystyle \frac{84}{16}$	$\displaystyle \frac{50}{16}$
$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
5	0	11111	1	$\displaystyle \frac{1}{32}$	$\displaystyle \frac{1}{32}$
5	1	111110 … 101111	$\displaystyle {5 \choose 1}=5$	$\displaystyle -\frac{1}{32}$	$\displaystyle -\frac{5}{32}$
5	2	1111100 … 1001111	$\displaystyle {6 \choose 2}=15$	$\displaystyle \frac{1}{32}$	$\displaystyle \frac{15}{32}$
5	3	11111000 … 10001111	$\displaystyle {7 \choose 3}=35$	$\displaystyle -\frac{1}{32}$	$\displaystyle -\frac{35}{32}$
5	4	111110000 … 100001111	$\displaystyle {8 \choose 4}=70$	$\displaystyle \frac{1}{32}$	$\displaystyle \frac{70}{32}$
5	5	1111100000 … 1000001111	$\displaystyle {9 \choose 5}=126$	$\displaystyle -\frac{1}{32}$	$\displaystyle -\frac{126}{32}$	$\displaystyle -\frac{80}{32}$
$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
6	0	111111	1	$\displaystyle \frac{1}{64}$	$\displaystyle \frac{1}{64}$
6	1	1111110 … 1011111	$\displaystyle {6 \choose 1}=6$	$\displaystyle -\frac{1}{64}$	$\displaystyle -\frac{6}{64}$
6	2	11111100 … 10011111	$\displaystyle {7 \choose 2}=21$	$\displaystyle \frac{1}{64}$	$\displaystyle \frac{21}{64}$
6	3	111111000 … 100011111	$\displaystyle {8 \choose 3}=56$	$\displaystyle -\frac{1}{64}$	$\displaystyle -\frac{56}{64}$
6	4	1111110000 … 1000011111	$\displaystyle {9 \choose 4}=126$	$\displaystyle \frac{1}{64}$	$\displaystyle \frac{126}{64}$	$\displaystyle \frac{86}{64}$
$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
7	0	1111111	1	$\displaystyle \frac{1}{128}$	$\displaystyle \frac{1}{128}$
7	1	11111110 … 10111111	$\displaystyle {7 \choose 1}=7$	$\displaystyle -\frac{1}{128}$	$\displaystyle -\frac{7}{128}$
7	2	111111100 … 100111111	$\displaystyle {8 \choose 2}=28$	$\displaystyle \frac{1}{128}$	$\displaystyle \frac{28}{128}$
7	3	1111111000 … 1000111111	$\displaystyle {9 \choose 3}=84$	$\displaystyle -\frac{1}{128}$	$\displaystyle -\frac{84}{128}$	$\displaystyle -\frac{62}{128}$
$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
8	0	11111111	1	$\displaystyle \frac{1}{256}$	$\displaystyle \frac{1}{256}$
8	1	111111110 … 101111111	$\displaystyle {8 \choose 1}=8$	$\displaystyle -\frac{1}{256}$	$\displaystyle -\frac{8}{256}$
8	2	1111111100 … 1001111111	$\displaystyle {9 \choose 2}=36$	$\displaystyle \frac{1}{256}$	$\displaystyle \frac{36}{256}$	$\displaystyle \frac{29}{256}$
$u(n)$	$z(n)$	$n_{2}$	Quanti	$f(n)$	Prodotti	Totale
9	0	111111111	1	$\displaystyle \frac{1}{512}$	$\displaystyle \frac{1}{512}$
9	1	1111111110 … 1011111111	$\displaystyle {9 \choose 1}=9$	$\displaystyle -\frac{1}{512}$	$\displaystyle -\frac{9}{512}$	$\displaystyle -\frac{8}{512}$
$u(n)$	$z(n)$	$n_{2}$	Quanti?	$f(n)$	Prodotti	Totale
10	0	1111111111	1	$\displaystyle \frac{1}{1024}$	$\displaystyle \frac{1}{1024}$	$\displaystyle \frac{1}{1024}$

La somma dei totali parziali

$\displaystyle 0+\frac{5}{4} - \frac{20}{8} + \frac{50}{16} - \frac{80}{32} + \frac{86}{64} - \frac{62}{128} + \frac{29}{256} - \frac{8}{512} + \frac{1}{1024}$

= $\displaystyle \frac{5\cdot 256 -20\cdot 128 +50\cdot 64 -80\cdot 32 + 86\cdot 16 -62 \cdot 8 +29 \cdot 4 -8\cdot 2 +1 \cdot 1}{1024}$

= $\displaystyle \frac{1280-2560+3200-2560+1376-496+116-16+1}{1024}$

= $\displaystyle \frac{341}{1024}$

La risposta al quesito: 341 + 1024 = 1365

Soluzione 3

Deve esistere una tecnica risolutiva più veloce!

???