Several distinct real numbers are written on a blackboard. Peter wants to create an algebraic expression such that among its values there would be these and only these numbers. He may use any real numbers, brackets, signs $+, -, \times$ and a special sign $\pm$. Usage of $\pm$ is equivalent to usage of $+$ and $-$ in all possible combinations. For instance, the expression $5 \pm 1$ results in $\{4, 6\}$, while $(2 \pm 0.5) \pm 0.5$ results in $\{1, 2, 3\}$. Can Peter construct an expression if the numbers on the blackboard are : (a) $1, 2, 4$ ? ($2$ points) (b) any $100$ distinct real numbers ? ($6$ points)
Problem
Source: Tournament of Town Fall 2015 Senior A-level
Tags: combinatorics, invariant
24.02.2017 14:07
We'll prove that Peter can construct an expression that yields any set of $n$ distinct reals, via induction on $n$. This nukes both (a) and (b) at the same time. The base case $n=1$ is trivial, so let's tackle the induction step. Suppose we can cook up an expression for any set with $n$ distinct reals. Consider the set $A=\{ a_1,a_2,\cdots ,a_{n+1}\}$; we'll prove that there's an expression for $A$ too. Consider the set $A'=\{ a_1-a_{n+1},a_2-a_{n+1},\cdots , a_n-a_{n+1}\}$. This has $n$ elements, so we should be able to make up an expression for $A'$ by induction hypothesis: call this expression $\mathcal{A}$. Consider the expression $$\mathcal A\times \left(\frac12{\color{blue}{\pm}}\frac12\right)+a_{n+1}.$$When that blue $\color{blue}\pm$ is interpreted as $+$, $\mathcal A$ covers all the numbers $a_i-a_{n+1}$ for $i\in\{1,\cdots ,n\}$, so $\mathcal A\times \left(\frac12+\frac12\right)+a_{n+1}=\mathcal A+a_{n+1}$ covers all the numbers $a_1,a_2,\cdots ,a_n$. The only other case is when $\color{blue}\pm$ is interpreted as $-$. Then the expression becomes $\mathcal A\times 0+a_{n+1}$, which takes care of $a_{n+1}$. So we're done! $\blacksquare$ Appendices: Just for fun, here's a simple python program for constructing the expression for any list of numbers. A=[]check=0while check==0: s=input('Type the (next) number (type \' done\' if you\'ve run out of numbers)') if s=='done': check=1 else: A.append(float(s))def sgnstr(x): if x>=0: return str(x) else: return '('+str(x)+')'def express(a): if len(a)==1: return str(a[0]) if len(a)>1: return '('+express([a[i]-a[-1] for i in range(len(a)-1)])+')x(0.5±0.5)+'+sgnstr(a[-1])print(express(A))A=[] check=0 while check==0: s=input('Type the (next) number (type \' done\' if you\'ve run out of numbers)') if s=='done': check=1 else: A.append(float(s)) def sgnstr(x): if x>=0: return str(x) else: return '('+str(x)+')' def express(a): if len(a)==1: return str(a[0]) if len(a)>1: return '('+express([a[i]-a[-1] for i in range(len(a)-1)])+')x(0.5±0.5)+'+sgnstr(a[-1]) print(express(A))RunResetPop Out / Also, here's the expression for $1,2,4$ generated by the process described above. $$\left(\left(-1\right)\times \left(\frac12\pm \frac12\right)+(-2)\right)\times \left(\frac12\pm \frac12\right)+4.$$
24.09.2017 11:14
Ankoganit wrote: We'll prove that Peter can construct an expression that yields any set of $n$ distinct reals, via induction on $n$. This nukes both (a) and (b) at the same time. The base case $n=1$ is trivial, so let's tackle the induction step. Suppose we can cook up an expression for any set with $n$ distinct reals. Consider the set $A=\{ a_1,a_2,\cdots ,a_{n+1}\}$; we'll prove that there's an expression for $A$ too. Consider the set $A'=\{ a_1-a_{n+1},a_2-a_{n+1},\cdots , a_n-a_{n+1}\}$. This has $n$ elements, so we should be able to make up an expression for $A'$ by induction hypothesis: call this expression $\mathcal{A}$. Consider the expression $$\mathcal A\times \left(\frac12{\color{blue}{\pm}}\frac12\right)+a_{n+1}.$$When that blue $\color{blue}\pm$ is interpreted as $+$, $\mathcal A$ covers all the numbers $a_i-a_{n+1}$ for $i\in\{1,\cdots ,n\}$, so $\mathcal A\times \left(\frac12+\frac12\right)+a_{n+1}=\mathcal A+a_{n+1}$ covers all the numbers $a_1,a_2,\cdots ,a_n$. The only other case is when $\color{blue}\pm$ is interpreted as $-$. Then the expression becomes $\mathcal A\times 0+a_{n+1}$, which takes care of $a_{n+1}$. So we're done! $\blacksquare$ Appendices: Just for fun, here's a simple python program for constructing the expression for any list of numbers. A=[]check=0while check==0: s=input('Type the (next) number (type \' done\' if you\'ve run out of numbers)') if s=='done': check=1 else: A.append(float(s))def sgnstr(x): if x>=0: return str(x) else: return '('+str(x)+')'def express(a): if len(a)==1: return str(a[0]) if len(a)>1: return '('+express([a[i]-a[-1] for i in range(len(a)-1)])+')x(0.5±0.5)+'+sgnstr(a[-1])print(express(A))A=[] check=0 while check==0: s=input('Type the (next) number (type \' done\' if you\'ve run out of numbers)') if s=='done': check=1 else: A.append(float(s)) def sgnstr(x): if x>=0: return str(x) else: return '('+str(x)+')' def express(a): if len(a)==1: return str(a[0]) if len(a)>1: return '('+express([a[i]-a[-1] for i in range(len(a)-1)])+')x(0.5±0.5)+'+sgnstr(a[-1]) print(express(A))RunResetPop Out / Also, here's the expression for $1,2,4$ generated by the process described above. $$\left(\left(-1\right)\times \left(\frac12\pm \frac12\right)+(-2)\right)\times \left(\frac12\pm \frac12\right)+4.$$ I'm afraid to say but about the code it doesn't actually work... when I click "done", then it says values doesn't exist
26.09.2017 07:34
@above Strange, works fine for me. Note that you're supposed to type "done", not click done (is there even such a button or something?).
27.09.2017 00:46
Ankoganit wrote: @above Strange, works fine for me. Note that you're supposed to type "done", not click done (is there even such a button or something?). Ah...