Numbers

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Numbers

G H J

Reveal topic tags

combinatorics unsolved

L

G H BBookmark kLocked kLocked NReply

Source: Canada Mathematical Olympiad 2007

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1270 posts

April

#1 h Aug 1, 2007, 5:30 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

For two real numbers $a$ , $b$ , with $ab\neq 1$ , define the $\ast$ operation by
$a\ast b=\frac{a+b-2ab}{1-ab}.$ Start with a list of $n\geq 2$ real numbers whose entries $x$ all satisfy $0<x<1$ . Select any two numbers $a$ and $b$ in the list; remove them and put the number $a\ast b$ at the end of the list, thereby reducing its length by one. Repeat this procedure until a single number remains.

$a.$ Prove that this single number is the same regardless of the choice of pair at each stage.
$b.$ Suppose that the condition on the numbers $x$ is weakened to $0<x\leq 1$ . What happens if the list contains exactly one $1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1044 posts

mszew

#2 h Aug 1, 2007, 11:58 AM • 2 Y

Y by Adventure10, Mango247

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16123 posts

JBL

#3 h Aug 1, 2007, 2:10 PM • 4 Y

Y by viperstrike, Adventure10, Mango247, and 1 other user

In fact, you need both that it's associative calculation and that it's commutative (this is obvious) and it follows that any chain can be rearranged into any other, so all give the same value. For part b, we also note that if $a \neq 1$ then $a * 1 = 1$ , so the result is 1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12096 posts

jmerry

#4 h Aug 1, 2007, 8:31 PM • 6 Y

Y by Adventure10, yofro, MS_asdfgzxcvb, and 3 other users

An algebraic interpretation of the operation:
Work in some commutative ring containing a copy of $\mathbb{R}$ , and let $N$ be a nonzero element with $N^{2}=0$ (for example, $A$ is the ring of polynomials mod $x^{2}$ and $N$ is $x$ ). If $\alpha=1+a(-1+N)$ and $\beta=1+b(-1+N)$ , then $\alpha\cdot\beta=(1-ab)+(a+b-2ab)(-1+N)=(1-ab)(1+a*b(-1+N))$ .

Since $a*b$ gives the coefficient ratio of the product of two elements with coefficient ratios $a$ and $b$ and the product is associative and commutative, $*$ is associative and commutative wherever it's defined. Coefficient ratios strictly between $-1$ and $1$ correspond to ring elements of the form $a+bN$ with $a$ positive; any products of these must still be of the same form. A coefficient ratio of $1$ is an element of the form $cN$ , and those absorb others under multiplication. A second such entry would collapse everything into being undefined, as $N^{2}=0$ , and zero has no coefficient ratio.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#5 h Aug 1, 2007, 8:38 PM • 4 Y

Y by Adventure10, Mango247, and 2 other users

Nice one, Jmerry; but how did you come up with that?

For me it was enough to observe that $\left(1-\frac{1}{x}\right)*\left(1-\frac{1}{y}\right)=1-\frac{1}{x+y-1}$ . This, however, has the downside that for part b) you either need to work in $\overline{\mathbb{R}}=\mathbb{R}\cup\left\{\infty\right\}$ or a separate argument...

Darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12096 posts

jmerry

#6 h Aug 3, 2007, 9:43 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

It reminded me of the angle addition identity for $\tan$ , and the relation of that identity to complex multiplication. As I was working through it, I realized that the "absorbing" value had to come from a nilpotent.
For the specific calculations, I wanted $(1+ak)(1+bk)=(1-ab)+(a+b-2ab)k$ ; that led to $k^{2}+2k+1=0$ . Setting $k=-1$ would cause all sorts of problems, so we use $k=-1+N$ instead.

This post has been edited 1 time. Last edited by darij grinberg, Aug 16, 2011, 12:38 PM
Reason: replaced "a_{b}-2ab" by "a+b-2ab"

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8 posts

Zagros

#7 h Apr 18, 2009, 10:38 AM • 2 Y

Y by Adventure10, Mango247

We see that

$\begin{eqnarray*}\frac{1}{1-a*b}-1 &=& \frac{1-ab}{ab-a-b+1}-1\\ &=&\frac{a+b-2ab}{ab-a-b+1}\\&=&\frac{(1-a)+(1-b)}{(1-a)(1-b)}-2\\&=&(\frac{1}{1-a}-1)+(\frac{1}{1-b}-1) \end{eqnarray*}$

Hence $S=\sum (\frac{1}{1-a}-1)$ is an invariant and the last number is $A=\frac{S}{S+1}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

755 posts

#8 h Apr 12, 2012, 1:54 AM • 1 Y

Y by Adventure10

OK can someone see if this solution makes sense? I thought of it relatively quickly and its very different than above answers (make sure i did not miss anything)

Obviously, $a*b=b*a$
Lemma: When $n=3$ , then any permutation over $a, b, c$ of $a*b*c$ are equivalent. Note: this is the $n=3$ case for part a
Proof: let $g(a,b,c)=(a*b)*c$ . Then
$g(a,b,c)=\frac{a+b-2ab}{1-ab} * c \\ = \frac{ \frac{a+b-2ab}{1-ab} + c - 2c(\frac{a+b-2ab}{1-ab})}{1-c(\frac{a+b-2ab}{1-ab})} (\frac{1-ab}{1-ab}) \\ = \frac{ a+b-2ab+c-abc-2c(a+b-2ab)}{1-ab-c(a+b-2ab)} \\ = \frac{a+b-2ab+c-abc-2ac-2bc+4abc}{1-ab-ac-bc+2abc} \\ = \frac{a+b+c-2ab-2bc-2ac+3abc}{1-ab-ac-bc+2abc}$
Which is obviously symmetric over $a,b,c \blacksquare$
Now we shall prove part a) by induction. The process in the problem is equivalent to producing some arrangement of the integers $x_1, x_2, ..., x_n$ with the $*$ operation between each pair of integers. We shall prove that, given an arbitrary arrangement of the integers $x_1, x_2, ..., x_n$ with a $*$ operation between each pair of integers, we can always reorder them to be in the order $x_1*x_2*...*x_n$ . This would imply that all orderings result in the same value, proving the problem.
$n=2$ is trivial because $a*b=b*a$ , and our proved $n=3$ , which is stating that $a*b*c=a*c*b=b*a*c=b*c*a=c*a*b=c*b*a$ . Now for the inductive step:

Given we can reorder an arbitrary arrangement $x_1, x_2, ..., x_n$ to be in the order $x_1*x_2*...*x_n$ , we shall prove we can do the same with a list of $n+1$ integers.
We start with an arrangement of $x_1, x_2, x_3, ..., x_n, x_{n+1}$ .
If the last element in our arrangement is $x_{n+1}$ , then the first $n$ elements are some arrangement of $x_1, x_2, ..., x_{n-1}, x_n$ , and we can rearrange the first $n$ elements to be in the order $x_1*x_2*...*x_n$ . Then our entire value becomes $x_1*x_2*...*x_n*x_{n+1}$ , and we are done.
Else, denote our last element to be $x_b$ .
if $b=1$ , then denote our second to last element $x_c$ . We can reorder the final two elements such that they switch from $...*x_c*x_b$ to $...*x_b*x_c$ . reassign b=c, so now our last element is $x_b, b \not=1$ .
then the first $n$ elements are some arrangement of $x_1,..., x_{n+1}$ , for all index $i, 1 \le i \le n+1, i \not= b$ . We can rearrange the first $n$ elements to be in ascending order, i. e. in the order $x_1*...*x_{n+1}$ for all index $i \not=b$ . Our entire value is then $x_1*...*x_{n+1}*x_b$ . We then rearrange the last $n$ elements to be in ascending order, such that our entire value is then $x_1*x_2*...*x_{n+1} \blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

803 posts

#9 h Apr 12, 2012, 10:01 AM • 1 Y

Y by Adventure10

We will prove that for any number of variables (say n>=2), the number obtained at last in this process is a symmetric expression in those variables.
we use induction (induction on n)
P(2),P(3) are true (easy to check)
we assume that P(k),P(k-1),...,P(2) is true [I.H.]
P(k+1)--
there are variables a 1,...a k, ,a (k+1)
now we choose any 2 variables a i and a j
then in the next stage , we have k variables a i*a j and the remaining k-1 variables of the previous stage ,i.e. k variables in total.
now , according to our I.H. , the number obtained at last is symmetric in these k variables of this stage ( as stated in the preceding line)
now , a i*a j is also symmetric in a i and a j
so, we can conclude that the expression is symmetric in a 1,..., a (k+1)
then it is easy to say that the last number is independent of the choice of variables in each stage

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1198 posts

#10 h Jun 7, 2016, 9:07 PM • 1 Y

Y by Adventure10

mathbuzz wrote:

We will prove that for any number of variables (say n>=2), the number obtained at last in this process is a symmetric expression in those variables.
we use induction (induction on n)
P(2),P(3) are true (easy to check)
we assume that P(k),P(k-1),...,P(2) is true [I.H.]
P(k+1)--
there are variables a 1,...a k, ,a (k+1)
now we choose any 2 variables a i and a j
then in the next stage , we have k variables a i*a j and the remaining k-1 variables of the previous stage ,i.e. k variables in total.
now , according to our I.H. , the number obtained at last is symmetric in these k variables of this stage ( as stated in the preceding line)
now , a i*a j is also symmetric in a i and a j
so, we can conclude that the expression is symmetric in a 1,..., a (k+1)
then it is easy to say that the last number is independent of the choice of variables in each stage

If I understand your solution correctly, I think it does not work.

What you are effectively claiming is the following: given a function f(x1,...xn) from R^n to R symmetric in x1,...,xn and a function g(p,q) from R^2 to R symmetric in p,q, then h(x1,...,xn-1,p,q)=f(x1,...xn-1, g(p,q)) is symmetric in x1,..xn,p,q.

But this is not true, for example take f=x+y+z, g=1/(p+q). Then h=x+y+1/(p+q). Clearly h(x,y,p,q) is identical to h(x,p,y,q).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

389 posts

alexanderhamilton124

#11 h Feb 27, 2025, 7:07 PM • 1 Y

Y by Nobitasolvesproblems1979

Note $\frac{a}{1 - a} + \frac{b}{1 - b} = \frac{\frac{a+b-2ab}{1-ab}}{1 - \frac{a+b-2ab}{1-ab}}$ , so the sum $\frac{x}{1 + x}$ for all numbers $x$ initially in the list is constant. So, the last number is a given. For the second part, note that performing any move with $1$ gives $1$ . So, there will always be a $1$ in the list, which means our last number is $1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

389 posts

alexanderhamilton124

#12 h Feb 27, 2025, 7:08 PM • 1 Y

Y by Nobitasolvesproblems1979

Note $\frac{a}{1 - a} + \frac{b}{1 - b} = \frac{\frac{a+b-2ab}{1-ab}}{1 - \frac{a+b-2ab}{1-ab}}$ , so the sum $\frac{x}{1 + x}$ for all numbers $x$ initially in the list is constant. So, the last number is a given. For the second part, note that performing any move with $1$ gives $1$ . So, there will always be a $1$ in the list, which means our last number is $1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

StrahdVonZarovich

2053 posts

StrahdVonZarovich

#13 h Feb 27, 2025, 7:16 PM • 1 Y

Y by alexanderhamilton124

isn't it enough to prove that $*$ is associative and commutative? it seems like that would be sufficient to prove that no matter which order a list of numbers is $*$ ed in, the result should be the same

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

389 posts

alexanderhamilton124

#14 h Mar 8, 2025, 10:46 AM

Y by

StrahdVonZarovich wrote:

isn't it enough to prove that $*$ is associative and commutative? it seems like that would be sufficient to prove that no matter which order a list of numbers is $*$ ed in, the result should be the same

Yes, that also works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

990 posts

#15 h Apr 8, 2025, 12:56 PM

Y by

a. Prove that $\star$ is associative and commutative, which should finish.
b. As $a \star 1 = 1$ , we have that $\star_{a \in A} a = 1$ if $1 \in A, |\{x \in A : x = 1\} = 1$ . (Here A is a *multiset*).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2957 posts

#16 h Apr 8, 2025, 1:38 PM

Y by

So how calculate , it is $x_1*x_2*...*x_{n+1} \blacksquare$ ?

This post has been edited 1 time. Last edited by teomihai, Apr 8, 2025, 1:39 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a