Maths Olympiad Prep

Track / Stage 7 / 194 of 300 #1594 of 1964

Problem 1594

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.4 Find the answer

Given X={0,a,b,c}X=\{0,a,b,c\}, let M(X)={ff:XX}M(X)=\{f|f: X\to X\} denote the set of all functions from XX into itself. An addition table on XX is given us follows:
++ 00 aa bb cc
00 00 aa bb cc
aa aa 00 cc bb
bb bb cc 00 aa
cc cc bb aa 00
a)If S={fM(X)f(x+y+x)=f(x)+f(y)+f(x)x,yX}S=\{f\in M(X)|f(x+y+x)=f(x)+f(y)+f(x)\forall x,y\in X\}, find S|S|.
b)If I={fM(X)f(x+x)=f(x)+f(x)xX}I=\{f\in M(X)|f(x+x)=f(x)+f(x)\forall x\in X\}, find I|I|.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

### Part (a)

1. **Understanding the Set S S **:
We need to find the set S S defined as:
S={fM(X)f(x+y+x)=f(x)+f(y)+f(x) x,yX} S = \{ f \in M(X) \mid f(x + y + x) = f(x) + f(y) + f(x) \ \forall x, y \in X \}
Given the addition table, we need to verify the condition f(x+y+x)=f(x)+f(y)+f(x) f(x + y + x) = f(x) + f(y) + f(x) for all x,yX x, y \in X .

2. Analyzing the Addition Table:
The addition table for X={0,a,b,c} X = \{0, a, b, c\} is:
+0abc00abcaa0cbbbc0accba0 \begin{array}{c|cccc} + & 0 & a & b & c \\ \hline 0 & 0 & a & b & c \\ a & a & 0 & c & b \\ b & b & c & 0 & a \\ c & c & b & a & 0 \\ \end{array}
We need to check the condition f(x+y+x)=f(x)+f(y)+f(x) f(x + y + x) = f(x) + f(y) + f(x) for all x,yX x, y \in X .

3. Verifying the Condition:
Let's verify the condition for each pair (x,y) (x, y) :
- For x=0 x = 0 :
f(0+y+0)=f(y)=f(0)+f(y)+f(0)    f(0)=0 f(0 + y + 0) = f(y) = f(0) + f(y) + f(0) \implies f(0) = 0
- For x=a x = a :
f(a+y+a)=f(0+y)=f(y)=f(a)+f(y)+f(a)    f(a)=0 f(a + y + a) = f(0 + y) = f(y) = f(a) + f(y) + f(a) \implies f(a) = 0
- For x=b x = b :
f(b+y+b)=f(0+y)=f(y)=f(b)+f(y)+f(b)    f(b)=0 f(b + y + b) = f(0 + y) = f(y) = f(b) + f(y) + f(b) \implies f(b) = 0
- For x=c x = c :
f(c+y+c)=f(0+y)=f(y)=f(c)+f(y)+f(c)    f(c)=0 f(c + y + c) = f(0 + y) = f(y) = f(c) + f(y) + f(c) \implies f(c) = 0

From the above, we see that f(x)=0 f(x) = 0 for all xX x \in X . Therefore, the only function in S S is the zero function.

4. **Counting the Elements in S S **:
Since the only function in S S is the zero function, we have:
S=1 |S| = 1

### Part (b)

1. **Understanding the Set I I **:
We need to find the set I I defined as:
I={fM(X)f(x+x)=f(x)+f(x) xX} I = \{ f \in M(X) \mid f(x + x) = f(x) + f(x) \ \forall x \in X \}
Given the addition table, we need to verify the condition f(x+x)=f(x)+f(x) f(x + x) = f(x) + f(x) for all xX x \in X .

2. Analyzing the Addition Table:
From the addition table, we have:
+0abc00abcaa0cbbbc0accba0 \begin{array}{c|cccc} + & 0 & a & b & c \\ \hline 0 & 0 & a & b & c \\ a & a & 0 & c & b \\ b & b & c & 0 & a \\ c & c & b & a & 0 \\ \end{array}
We need to check the condition f(x+x)=f(x)+f(x) f(x + x) = f(x) + f(x) for all xX x \in X .

3. Verifying the Condition:
Let's verify the condition for each x x :
- For x=0 x = 0 :
f(0+0)=f(0)=f(0)+f(0)    f(0)=0 f(0 + 0) = f(0) = f(0) + f(0) \implies f(0) = 0
- For x=a x = a :
f(a+a)=f(0)=f(a)+f(a)    0=f(a)+f(a)    f(a)=0 f(a + a) = f(0) = f(a) + f(a) \implies 0 = f(a) + f(a) \implies f(a) = 0
- For x=b x = b :
f(b+b)=f(0)=f(b)+f(b)    0=f(b)+f(b)    f(b)=0 f(b + b) = f(0) = f(b) + f(b) \implies 0 = f(b) + f(b) \implies f(b) = 0
- For x=c x = c :
f(c+c)=f(0)=f(c)+f(c)    0=f(c)+f(c)    f(c)=0 f(c + c) = f(0) = f(c) + f(c) \implies 0 = f(c) + f(c) \implies f(c) = 0

From the above, we see that f(x)=0 f(x) = 0 for all xX x \in X . Therefore, the only function in I I is the zero function.

4. **Counting the Elements in I I **:
Since the only function in I I is the zero function, we have:
I=1 |I| = 1

The final answer is S=1 \boxed{ |S| = 1 } and I=1 |I| = 1 .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.