Switchable Valued Function

Algebra Level 4

$f$ is defined in $\mathbb{Z^+}$ such that
$f(x,x) = x \\ f(x,y) = f(y,x) \\ (x+y)f(x,y) = yf(x,x+y). \\$

Find the value of $f(14,52)$ .

The answer is 364.

3 solutions

Chew-Seong Cheong
Mar 22, 2016

Yes, as 展豪張 mentioned $f(x, y) =\text{lcm} (x, y)$ . We note that $\text{lcm} (x, x) =x$ and $\text{lcm} (x, y) =\text{lcm} (y, x)$ . Using $\text{lcm} (x, y) = \dfrac{xy}{\text{gcd} (x, y)}$ , we find that:

$\begin{aligned} (x+y) f(x, y) & = yf(x, x+y) \\ (x+y)\frac{xy}{\text{gcd} (x, y)} & = y\frac{x(x+y)}{\text{gcd} (x, x+y)} \\ \frac{xy(x+y)} {\text{gcd} (x, y)}& \equiv \frac{xy(x+y)} {\text{gcd} (x, y)} \end{aligned}$

Therefore $f(14,52)=\text{lcm} (14,52) = \boxed{364}$

We can also solve it using the definition.

$\begin{aligned} (x+y) f(x, y) & = yf(x, x+y) \\ \Rightarrow f(x, x+y) & =\frac {x+y} {y} \times f(x, y) \\ f(2,4) &= \frac{4}{2}\times f(2,2)=4 \\ f(4,6) &= \frac{6}{2}\times f(4,2)=12 \\ f(4,10) &= \frac{10}{6}\times f(4,6)=20 \\ f(10,14) &= \frac{14}{4}\times f(10,4)=70\\ f(14,24) &= \frac{24}{10}\times f(14,10)=168 \\ f(14,38) &= \frac{38}{24}\times f(14,24)= 266 \\ f(14,52) &= \frac{52}{38}\times f(14,38)= \boxed{364} \end{aligned}$

Great solution!

Swapnil Das - 5 years, 2 months ago

Did it the same way.

Archit Agrawal - 5 years, 2 months ago

Nice proof!

展豪張 - 5 years, 2 months ago

Nice insight.

In the first half of the solution, you showed that "LCM function satisfies these conditions".However, this doesn't yet prove that the LCM function is the unique function which satisfies these conditions.

Calvin Lin Staff - 5 years, 2 months ago

Let me try to prove it.

If $x=y=0$ ,
$f(x,y)=f(0,0)=0=\text{lcm}(x,y)$
$\square$

If $x=0$ or $y=0$ (but not both),
Since $f(x,y)=f(y,x)$ , WLOG we let $y=0$ .
Using the third condition,
$(x+0)f(x,0)=0f(x,x+0)$
i.e. $f(x,0)=0$
$\therefore f(x,0)=\text{lcm}(x,0)$
$\square$

Let $g(x,y)=\dfrac{xy}{f(x,y)}$ (the zero cases have been handled separately, so this can be defined)
Rewriting all three conditions from ' $f$ -form' to ' $g$ -form':
$g(x,x)=x$
$g(x,y)=g(y,x)$
$g(x,x+y)=g(x,y)$
By applying these properties 'wisely', $g$ is the Euclidean Algorithm.
So $g=\text{gcd}$ .
$f(x,y)=\dfrac{xy}{g(x,y)}=\dfrac{xy}{\text{gcd}(x,y)}=\text{lcm}(x,y)$
$\square$

All cases have been handled, so the proof is done. =D

展豪張 - 5 years, 2 months ago

No, not quite. You are still committing the same mistake:

When solving a functional equation, it is not sufficient to just check that a specially chosen function satisfies the conditions given, because there could be alternative solutions to it.

E.g. if we wanted to solve $f(x) f(\frac{1}{x} ) = 1 , f(1) = 1$ , we cannot simply say " $f(x) = x$ satisfies the conditions, so that's the solution".

Calvin Lin Staff - 5 years, 2 months ago

@Calvin Lin – But the output of the Euclidean Algorithm is unique...

展豪張 - 5 years, 2 months ago

@展豪張 – Indeed, so that's one missing (unstated) piece of the puzzle. It boils down to showing that the function is uniquely determined, based on the conditions. We can go about this in multiple ways, like inducting on $\max (x,y)$ .

Calvin Lin Staff - 5 years, 2 months ago

@Calvin Lin – Thanks for the comments. I suspected the proof was not complete but did not know how to proceed. I still have to think about it now.

Chew-Seong Cheong - 5 years, 2 months ago

@Calvin Lin – Oh I got it... Thank you! :)

展豪張 - 5 years, 2 months ago

展豪張
Mar 22, 2016

Rewrite the third statement as $f(x,x+y)=\dfrac{x+y}yf(x,y)$
$y\mapsto y-x,f(x,y)=\dfrac y{y-x}f(x,y-x)$ which allows us to 'reduce' the parameter.
Statement 2 allows us to swap the two parameter.
After some computation the answer is $364$ .
(I guess this function is $lcm$ function......maybe I will prove it later......)

Abhi Kumbale
Mar 24, 2016

Switchable Valued Function

The answer is 364.

3 solutions

0 pending reports