1. Очевидно, всяко цяло число, по-голямо или равно на k, е стойност на f.
2. Да разгледаме израза f(f(f(n))):
f(f(f(n))) = f(n+k), но също и f(f(f(n))) = f(n)+k.
Значи, f(n+k) = f(n)+k.
3. По индукция следва, че f(n+sk) = f(n)+sk
4. В частност, функцията е напълно определена, ако се знаят стойностите f(0), f(1), f(2), ..., f(k-1).
5. Въвеждаме помощната функция F(n) = f(n) mod k. От т.2 следва, че F(n+k) = F(n), т.е. F е периодична с период k.
6. От функционалното уравнение следва, че за n=0,1,...,k-1 имаме F(f(n)) = n.
7. Но f(n) = F(n) + sk поради дефиницията на F, значи F(F(n)+sk) = n. Понеже F е периодична, то F(F(n)) = n
8. С други думи, ако разглеждаме F в множеството {0,1,...k-1}, то тя съвпада със своята обратна: ако F(n) = m , то F(m) = n
9. Не може F(m) = m. Наистина, да допуснем противното. Тогава f(m) = F(m)+sk = m+sk, значи f(m+sk) = f(f(m)) = m+k. От друга страна, по т.3 следва, че f(m+sk) = f(m) + sk = m+2sk. Следователно (понеже k > 0), s = 1/2, което е невъзможно, понеже s е цяло.
10. И така, множеството {0,1,2,...,k-1} се разбива на ненаредени двойки {m,n}, такива, че F(m) = n, F(n) = m, m <> n и всяко число от {0,1,2,...,k-1} участва само в една такава двойка.
11. Нека n е от множеството {0,1,2,...,k-1}, m = F(n). Тогава f(n) = F(n) + rk = m+rk. Следва, че n+k = f(f(n)) = f(m+rk) = f(m)+rk = F(m)+sk+rk = n+(s+r)k. Значи, r+s = 1, т.е. r = 0, s = 1 или обратно. Тоест, f(n) = m+r(n)k, където r e 0 или 1, при това, ако r(n) = 0, то r(m) = 1 и обратно. С други думи, във всяка от двойките {n, m} на едното число съответства 1, а на другото - 0.
12. Намерените дотук условия са достатъчни (досега показахме, че са необходими): нека вземем произволно разбиване на {0,1,2,...,k-1} на ненаредени двойки {n,m}, такива, че n <> m и всяко число участва точно в една двойка. На всяко от тези n да съпоставим r(n) - 0 или 1, и то така, че ако r(n) = 0, то r(m) = 1 и обратно. Тогава f(n+sk)=m+r(n)k+sk удовлетворява функционалното уравнение, което се вижда с непосредствена проверка:
f(f(n)) = f(m+r(n)k) = f(m)+r(n)k = n+r(m)k+r(n)k = n+k
13. Значи, броят на функциите е рявен на броя на начините, по които може да се осъществи такова разбиване, а именно: разделяне на две групи от по k/2 елемента може да стане по C(k,k/2) начина. На всеки елемент от едната група трябва да се съпостви елемент от другата (n<->m), това може да стане по P(k/2) начина (разместваме елементите на втората група). Най-сетне, на всяка двойка трябва да съпоставим (1; 0) или (0; 1), т.е. общо 2^(k/2) възможности.
14. Всичко C(k,k/2).P(k/2).2^(k/2)
= ( 2^(k/2) ) (k(k-1)(k-2)...(k/2+1) функции
Автор
Тема: Edna ne mnogo trudna zadacha (2) (Прочетена 1342 пъти)