20
$\begingroup$

A nice easy puzzle for the math lovers out there.

We're all familiar with the $\max$ function: $$\max \left( {x,y} \right) \triangleq \left\{ {\begin{array}{*{20}{l}} x&{{\text{if }}x \geq y} \\ y&{{\text{otherwise}}} \end{array}} \right.\,\,\,\forall\, x,y \in \mathbb{R}$$

Suppose we wish to implement this function using no conditional logic and only a basic set of operations:

  • multiplication, division, addition, and subtraction
  • real-valued numeric constants
  • the floor function, $\left\lfloor \cdot \right\rfloor$, which yields the greatest integer $\leq$ its argument (e.g. $\left\lfloor -1.5 \right\rfloor = -2$)

Question

Can you realize the $\max$ function for all real inputs using only these basic operations?

$\endgroup$
  • $\begingroup$ I understood everything you said except what do you mean 'realize the max function' $\endgroup$ – CyanogenCX Jun 18 '15 at 1:30
  • $\begingroup$ @CyanogenCX: I mean "Can you build the $\max$ function out of these more primitive functions?" The aim is to show how you can compute the maximum of $x$ and $y$ using only the set of operations listed. $\endgroup$ – COTO Jun 18 '15 at 1:34
  • $\begingroup$ Makes me wonder. is there a way to do this without the floor function? $\endgroup$ – Ivo Beckers Jun 18 '15 at 12:55
  • $\begingroup$ @IvoBeckers: You'd be limited to constructing rational functions (i.e. ratios of polynomials). I'm all but positive it wouldn't be possible to realize something as exotic as $\max$. If you (or any reader) figures out a way to do it, post it as an answer and I'll award it a 200 rep bounty out of being singularly impressed. ;) $\endgroup$ – COTO Jun 18 '15 at 15:01
26
$\begingroup$

The graph of $f(x):=x\cdot(1+x^2)^{-1}$ looks like:

enter image description here

This function satisfies $$ \big\lfloor f(x)\big\rfloor =\begin{cases}0:&x\geq 0,\\-1:&x<0. \end{cases} $$ Using this, we can check that the function $$ x-\left\lfloor\frac{x-y}{1+(x-y)^2}\right\rfloor(y-x)= x-\big\lfloor f(x-y)\big\rfloor(y-x) $$ takes the value $\max\{x,y\}$:

  • if $x\geq y$, then $\big\lfloor f(x-y)\big\rfloor =0$, so $x-\big\lfloor f(x-y)\big\rfloor(y-x)=x-0\cdot(y-x) =x$,

  • if $x<y$, then $\big\lfloor f(x-y)\big\rfloor =-1$, so $x-\big\lfloor f(x-y)\big\rfloor(y-x)=x-(-1)\cdot(y-x) =y$.

$\endgroup$
  • $\begingroup$ You got it. I used exactly the same $f\left( x\right)$ but your second step is simpler (I used $\left| x\right|$ as an intermediary). $\endgroup$ – COTO Jun 18 '15 at 2:29
  • $\begingroup$ Could you please explain the answer in a much simpler way? I can not understand this. Thank you. $\endgroup$ – Cows quack Jun 18 '15 at 9:49
  • 4
    $\begingroup$ LOL. I love it when people ( preferable with good mathematics background ) say "It is not hard to see..." Reminds me of the good old days at university. But no, for people with less mathematical background it is far less easy to see. It can't hurt to edit in one or two sentences... (But yes, I do see the solution.) $\endgroup$ – BmyGuest Jun 18 '15 at 11:38
  • 1
    $\begingroup$ @BmyGuest [How those without 'good' mathematical intuition see it] 1 + 1 = 2...From here, it's not hard to see how we get the answer x - floor[frac{x-y}{1+(x-y)^2}] * (y-x)= x - floor[ f(x-y)] * (y-x)... $\endgroup$ – Mark N Jun 18 '15 at 13:23
  • $\begingroup$ Sorry, I've acquired some bad habits through years of writing for other mathematicians. I added some more explanation. $\endgroup$ – Julian Rosen Jun 18 '15 at 14:39
7
$\begingroup$

I came up with this: $$ \frac{\big\lfloor\frac{x}{y}\big\rfloor\cdot x+\big\lfloor\frac{y}{x}\big\rfloor\cdot y}{\big\lfloor\frac{x}{y}\big\rfloor+\left\lfloor\frac{y}{x}\right\rfloor} $$ If $x$ is higher, then $\big\lfloor\frac{y}{x}\big\rfloor = 0$ and the fraction above equals $x$, same if $y$ is higher.

If $x=y$, then $\big\lfloor\frac{x}{y}\big\rfloor =\big\lfloor\frac{y}{x}\big\rfloor = 1$, and the fraction equals $\frac{x + y}{2}$, which is $\frac{2x}{2} = x$ (because $x = y$).

$\endgroup$
  • 4
    $\begingroup$ Doesn't this fail if x or y are 0 because some of the fractions will be undefined? $\endgroup$ – Beska Jun 18 '15 at 13:44
  • 1
    $\begingroup$ It's a neat concept, but Beska is right: we run into division-by-zero problems in some instances. $\endgroup$ – COTO Jun 18 '15 at 14:52
  • $\begingroup$ True, I completely overlooked the division by zero problem that appears... back to the drawing board, I guess :) $\endgroup$ – Sleku Jun 18 '15 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.