PUMaC 2009 · 代数（B 组） · 第 8 题

PUMaC 2009 — Algebra (Division B) — Problem 8

Find the number of functions f : Z 7 → Z for which f ( h + k ) + f ( hk ) = f ( h ) f ( k ) + 1, for all integers h and k . 1

解析

Find the number of functions f : Z 7 → Z for which f ( h + k ) + f ( hk ) = f ( h ) f ( k ) + 1, ∀ h, k ∈ Z . 2 Solution. 3. Putting ( h, k ) = (0 , 0) we get ( f (0) − 1) = 0 hence f (0) = 1. Then let ( h, k ) = (1 , − 1) to find f (0) + f ( − 1) = f (1) f ( − 1) + 1 hence f ( − 1)( f (1) − 1) = 0. So there are two cases: first, if f (1) = 1, then letting ( h, k ) = (1 , k ) yields f (1 + k ) + f ( k ) = f (1) f ( k ) + 1, or also f ( k +1) = 1, that is f is constant, equal to 1. The second case is f ( − 1) = 0, and then we let ( h, k ) = ( − 1 , − 1) to get f ( − 2) + f (1) = 1, and ( h, k ) = (1 , − 2) to get f ( − 2) = f (1) f ( − 2) + 1. From the first equation we can express f ( − 2) = 1 − f (1) and substitute this into the second 2 one: 1 − f (1) = f (1)(1 − f (1))+1 or also (1 − f (1)) = 1. Hence there are two subcases: f (1) is 0 or 2. Recall that f (1+ k )+ f ( k ) = f (1) f ( k )+1. If f (1) = 0, this becomes f (1+ k ) = 1 − f ( k ) k 1+( − 1) and since f (0) = 1 the function takes the values 0 and 1 alternately: f ( k ) = . On the 2 other hand, if f (1) = 2, then the equation becomes f (1 + k ) = f ( k ) + 1, hence f ( k ) = k + 1 k 1+( − 1) for all k . We obtained 3 solutions: f = 1, f ( k ) = and f ( k ) = k + 1. 2 3