Klub 44M - zadania II 2011»Zadanie 615
o zadaniu...
- Zadanie pochodzi z artykułu Klub 44M - zadania II 2011
- Publikacja w Delcie: luty 2011
- Publikacja elektroniczna: 1 lutego 2011
- Artykuł źródłowy w wersji do druku [application/pdf]: (206 KB)
Każdemu podzbiorowi
zbioru
, który nie zawiera
żadnej pary liczb kolejnych, przyporządkowujemy liczbę
, będącą
iloczynem liczb w zbiorze
(dla zbioru pustego przyjmujemy
). Obliczyć sumę kwadratów wszystkich uzyskanych
liczb

Weźmy pod uwagę wszystkie te
podzbiory
zbioru
które nie zawierają żadnej pary
liczb kolejnych i do których nie należy liczba
Są to więc podzbiory
zbioru
; suma kwadratów uzyskanych dla nich liczb
wynosi
Z kolei zbiory
(bez pary liczb
kolejnych), do których liczba
należy, traktujemy jak podzbiory zbioru
z dołączonym elementem
; suma kwadratów
uzyskanych dla nich liczb
wynosi
Dostajemy wzór
rekurencyjny
który z wartościami początkowymi
prowadzi przez łatwą indukcję do wyniku w jawnej
postaci: