Maths Olympiad Prep

Library / /348 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Find the answer

The equatorial algebra is defined as the real numbers equipped with the three binary operations \natural, \sharp, \flat such that for all x,yRx, y\in \mathbb{R}, we have xy=x+y,xy=max{x,y},xy=min{x,y}.x\mathbin\natural y = x + y,\quad x\mathbin\sharp y = \max\{x, y\},\quad x\mathbin\flat y = \min\{x, y\}.
An equatorial expression over three real variables xx, yy, zz, along with the complexity of such expression, is defined recursively by the following:
[list]
[*] xx, yy, and zz are equatorial expressions of complexity 0;
[*] when PP and QQ are equatorial expressions with complexity pp and qq respectively, all of PQP\mathbin\natural Q, PQP\mathbin\sharp Q, PQP\mathbin\flat Q are equatorial expressions with complexity 1+p+q1+p+q.
[/list]
Compute the number of distinct functions f:R3Rf: \mathbb{R}^3\rightarrow \mathbb{R} that can be expressed as equatorial expressions of complexity at most 3.

Proposed by Yannick Yao

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve the problem, we need to compute the number of distinct functions f:R3R f: \mathbb{R}^3 \rightarrow \mathbb{R} that can be expressed as equatorial expressions of complexity at most 3. We will analyze the problem by considering the complexity of the expressions step by step.

1. Complexity 0:
- The expressions are simply the variables x x , y y , and z z .
- Therefore, there are 3 distinct functions: x x , y y , and z z .

2. Complexity 1:
- We can form expressions by combining two variables using the operations \natural , \sharp , and \flat .
- The possible pairs of variables are (x,y) (x, y) , (x,z) (x, z) , and (y,z) (y, z) . Each pair can be combined in 3 ways.
- Additionally, we can combine a variable with itself, but this does not create new functions since xx=x x \sharp x = x , xx=x x \flat x = x , and xx=2x x \natural x = 2x .
- Therefore, the number of distinct functions is 3×3+3=12 3 \times 3 + 3 = 12 .

3. Complexity 2:
- We can form expressions by combining a complexity 1 expression with a variable using the operations \natural , \sharp , and \flat .
- We need to consider the forms F1(F2(u,v),w) F_1(F_2(u, v), w) where F1 F_1 and F2 F_2 are operations and u,v,w u, v, w are variables.
- We will analyze the cases where F1=F2 F_1 = F_2 and F1F2 F_1 \neq F_2 .

**Case 2.1: F1=F2 F_1 = F_2 **
- If F1=F2= F_1 = F_2 = \natural , the expressions are of the form (u+v)+w (u + v) + w . There are 3 choices for u,v,w u, v, w giving 3!=6 3! = 6 distinct functions.
- If F1=F2= F_1 = F_2 = \sharp or F1=F2= F_1 = F_2 = \flat , the expressions are max(max(u,v),w) \max(\max(u, v), w) and min(min(u,v),w) \min(\min(u, v), w) respectively. Each has 1 distinct function.

**Case 2.2: F1F2 F_1 \neq F_2 **
- If one of F1 F_1 or F2 F_2 is \natural , we have expressions like max(u,v)+w \max(u, v) + w or min(u,v)+w \min(u, v) + w . Each combination of operations and variables gives distinct functions.
- If F1= F_1 = \sharp and F2= F_2 = \flat (or vice versa), we have expressions like max(min(u,v),w) \max(\min(u, v), w) . Each combination of operations and variables gives distinct functions.

Summarizing the counts:
- F1=F2= F_1 = F_2 = \natural : 6 functions.
- F1=F2= F_1 = F_2 = \sharp or F1=F2= F_1 = F_2 = \flat : 2 functions.
- F1F2 F_1 \neq F_2 with one \natural : 54 functions.
- F1= F_1 = \sharp and F2= F_2 = \flat (or vice versa): 6 functions.

4. Complexity 3:
- We can form expressions by combining two complexity 2 expressions or by combining a complexity 2 expression with a variable.
- We need to consider the forms F1(F2(u,v),F3(w,t)) F_1(F_2(u, v), F_3(w, t)) and F1(F2(F3(u,v),w),t) F_1(F_2(F_3(u, v), w), t) .

**Case 3.1: F1(F2(u,v),F3(w,t)) F_1(F_2(u, v), F_3(w, t)) **
- We analyze the cases where all operations are the same or different.
- If all operations are \natural , we have expressions like (u+v)+(w+t) (u + v) + (w + t) . There are 15 distinct functions.
- If all operations are \sharp or \flat , we have expressions like max(max(u,v),max(w,t)) \max(\max(u, v), \max(w, t)) . Each has 1 distinct function.
- If one operation is \natural , we have expressions like min(u,v)+max(w,t) \min(u, v) + \max(w, t) . Each combination of operations and variables gives distinct functions.
- If two operations are \natural , we have expressions like min(u+v,w+t) \min(u + v, w + t) . Each combination of operations and variables gives distinct functions.

**Case 3.2: F1(F2(F3(u,v),w),t) F_1(F_2(F_3(u, v), w), t) **
- We analyze the cases where all operations are the same or different.
- If all operations are \natural , we have expressions like ((u+v)+w)+t ((u + v) + w) + t . There are 15 distinct functions.
- If all operations are \sharp or \flat , we have expressions like max(max(u,v),w) \max(\max(u, v), w) . Each has 1 distinct function.
- If one operation is \natural , we have expressions like max(u+v,w)+t \max(u + v, w) + t . Each combination of operations and variables gives distinct functions.
- If two operations are \natural , we have expressions like max(u+v,w+t) \max(u + v, w + t) . Each combination of operations and variables gives distinct functions.

Summarizing the counts:
- F1(F2(u,v),F3(w,t)) F_1(F_2(u, v), F_3(w, t)) : 15 + 1 + 1 + 6 + 12 + 72 + 30 - 6 - 6 - 12 + 36 = 168 functions.
- F1(F2(F3(u,v),w),t) F_1(F_2(F_3(u, v), w), t) : 15 + 1 + 1 + 6 + 12 + 72 + 30 - 6 - 6 - 12 + 36 = 168 functions.

Adding all the counts together:
- Complexity 0: 3 functions.
- Complexity 1: 12 functions.
- Complexity 2: 6 + 2 + 54 + 6 = 68 functions.
- Complexity 3: 168 + 168 = 336 functions.

Total number of distinct functions: 3+12+68+336=419 3 + 12 + 68 + 336 = 419 .

The final answer is 419 \boxed{419} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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