3
$\begingroup$

META: I wrote the explanation for this problem assuming a monospace font... it might be easier to read if you copy and paste it into a text file and view it separately. Or, if you know how, feel free to edit it to have a monospace font with automatic line breaks because I don't know how.

Let 4 variables $a,b,c,d$ be rationals in $[0,1]$ which, when multiplied by $255$, become integers. (That is, $a,b,c,d\in \{\frac{x}{255}\mid 0\leq x\leq 255,\ x\in\mathbb{Z}\}$. Examples of valid values are $1/255$, $2/255$, $3/255$, etc.

The variables are related in one equation. I want to prove that there are no solutions to this equation, by which I mean there are no valid values for the 4 variables that will satisfy the equation. $\frac{ac + (1-a)bd}{a+(1-a)b} = \frac{1}{2}$

Now I'm going to redefine $a,b,c,d$ to be non-negative integers in the domain $[0,255]$. The equation will still hold if I add the denominator $255$ to the variables. $\begin{align*} \frac{\frac{a}{255}\;\frac{c}{255} + \left(1-\frac{a}{255}\right)\frac{b}{255}\;\frac{d}{255}}{\frac{a}{255} + \left(1 - \frac{a}{255}\right)\frac{b}{255}} &= \frac{1}{2}\\ \frac{\frac{ac}{255^2} + \frac{(255-a)bd}{255^3}}{\frac{a}{255}+\frac{(255-a)b}{255^2}} &= \frac{1}{2}\\ \frac{\quad\frac{255ac + (255-a)bd}{255^3}\quad}{\frac{255a + (255-a)b}{255^2}}&=\frac{1}{2}\\ \frac{255 ac + (255-a)bd}{255^3}\;\frac{255^2}{255a+(255-a)b} &= \frac{1}{2}\\ \frac{255ac + (255-a)bd}{255(255a + (255-a)b)}&=\frac{1}{2}\\ \frac{255 ac + (255-a)bd}{255^2a + 255(255-a)b}&=\frac{1}{2}. \end{align*}$

$a,b,c,d$ are non-negative integers in the domain $[0,255]$. Is it possible to prove that there are no solutions to this equation?

One way to determine this is to test all ($255^4=4228250625$) possible combinations, however I'm looking for a more compelling proof.

Both the numerator and denominator will each evaluate to a non-negative integer value. That being said, a part of the set of possible evaluated fractions will look like this: $\frac{1}{2}, \frac{2}{4}, \frac{3}{6},\frac{4}{8},\frac{5}{10},\frac{6}{12},\frac{7}{14},\frac{8}{16},\frac{9}{18},\frac{10}{20},\ldots$

The denominator must evaluate to an even number.

Here are some of the rules of parity (even or odd) arithmetic:

Addition/subtraction:

      Even Odd      __________ Even |Even Odd Odd  |Odd  Even 

Multiplication:

      Even Odd      __________ Even |Even Even Odd  |Even Odd 

The denominator has only two variables $a$ and $b$ that I need to worry about. Let's consider the possible cases of parity and see which combinations result in an even number.

$255^2a + 255(255-a)b$ $(\mathrm{Odd})a + (\mathrm{Odd})((\mathrm{Odd})-a)b$

$a$: Even; $b$: Even (Odd)(Even) + (Odd)((Odd)-(Even))(Even) (Even) + (Odd)(Odd)(Even) (Even) + (Odd)(Even) (Even) + (Even) (Even)  a: Odd; b: Even (Odd)(Odd) + (Odd)((Odd)-(Odd))(Even) (Odd) + (Odd)(Even)(Even) (Odd) + (Even)(Even) (Odd) + (Even) (Odd)  a: Even; b: Odd (Odd)(Even) + (Odd)((Odd)-(Even))(Odd) (Even) + (Odd)(Odd)(Odd) (Even) + (Odd)(Odd) (Even) + (Odd) (Odd)  a: Odd; b: Odd (Odd)(Odd) + (Odd)((Odd)-(Odd))(Odd) (Odd) + (Odd)(Even)(Odd) (Odd) + (Even)(Odd) (Odd) + (Even) (Odd) 

Therefore, the denominator is only even when both $a$ and $b$ are even. Let's see the parity of the numerator with $a$ and $b$ both being even.

$255ac + (255-a)bd$

(Odd)(Even)c + ((Odd)-(Even))(Even)d (Even)c + (Odd)(Even)d (Even)c + (Even)d (Even) + (Even) (Even) 

Therefore, the numerator must be an even number as well, reducing the set of possible evaluated fractions to those with even numerators: $\frac{2}{4},\frac{4}{8},\frac{6}{12},\frac{8}{16},\frac{10}{20},\ldots$

.. this is the furthest I could go with my insular analysis. Are there any other rules I could use to reduce the set of possible evaluated fractions down to 0?

  • 0
    @Arturo: Not$a$problem!2012-02-18

1 Answers 1

2

You are really trying to solve the diophantine equation $510 ac + (510-2a)bd = 255^2a + 255(255-a)b$ with $0\leq a,b,c,d\leq 255$, $a^2+b^2\gt 0$ (so the denominator is not zero).

The left hand side is even; for the right hand side to be even, we either need $a$ to be even (so $255^2a$ to be even) and $b$ even (so $255(255-a)b$ will also be even); or $255^2a$ odd and $255(255-a)b$ odd; but $a$ odd implies $255-a$ even, so this is impossible.

Modulo $3$, we have $-2abd \equiv 0\pmod{3}$, so one of $a,b,d$ must be a multiple of $3$

Modulo $5$, we have $-2abd \equiv 0\pmod{5}$, so one of $a$, $b$, $d$ must be a multiple of $5$.

Modulo $17$ (why $17$? Because $255=3\times 5\times 17$) we also have $-2abd\equiv 0\pmod{17}$, so one of $a,b,d$ must be a multiple of $17$.

This led me to consider whether the conditions could be satisfied by the same one of $a,b,d$. If it is $a$ or $b$, then they are forced to be $0$ by the conditions above.

If $a=0$, we get $510bd = 255^2b$; or $2d = 255$, which is impossible. If $b=0$, then we get $510ac = 255^2a$, or $2c=255$, again impossible.

Now, $d$ can satisfy the condition either as $d=0$ or $d=255$. If $d=0$, then we get $510ac = 255^2a + 255(255-a)b$ which reduces to $2ac = 255a + (255-a)b$ or $b = \frac{2ac-255a}{255-a} = \frac{(2c-255)a}{255-a}.$ For $b$ to be nonnegative, we need $c\gt 127$. But I found a way to make all values work: take $c=150$, $a=210$; then $b=\frac{(300-255)210}{255-210} = \frac{(45)(210)}{45} = 210.$ So, we can try $a=b=210$, $c=150$, $d=0$; indeed, $\begin{align*} \frac{255 ac + (255-a)bd}{255^2a + 255(255-a)b}&= \frac{255(210)(150) + (255-210)(210)(0)}{255^2(210) + 255(255-210)(210)}\\ &= \frac{(255)(210)(150)}{(255)(210)(255+45)}\\ &= \frac{150}{300} = \frac{1}{2}. \end{align*}$ Or in your original equation, $d=\frac{0}{255}$, $a=b=\frac{210}{255}$, $c=\frac{150}{255}$. There are probably other solutions.

If $d=255$ (for completeness), we get $510 ac + (510-2a)bd = 255^2a + 255(255-a)b$ which simplifies: $\begin{align*} 510ac + 255(510-2a)b &= 255^2a + 255(255-a)b\\ 255(2ac + (510-2a)b) &= 255(255a + (255-a)b)\\ 2ac + (510-2a)b &= 255a + (255-a)b\\ 2ac - 255a &= (255-a)b - 2(255-a)b\\ 2ac - 255a &= -(255-a)b\\ \frac{a(255-2c)}{255-a} &= b \end{align*}$ which is just the dual of the last solution. For example, taking $a=210$ again, we can take $c=105$ to get $b=210$ as another solution. Note that this $c$ is just the complement of the previous $c$ relative to $255$.


And we get an easy family of solutions, all with $a=b$: take $a=b=2k$, $0\leq k\leq 127$, $c=k$, $d=255$; or $a=b=2k$, $c=255-k$, $d=0$.

The above analysis does not necessarily exhaust all possible solutions, but since you said you only wanted to prove that there were no solutions (which is unfortunately not the case), I stopped there. I don't know if there are any solutions with $a\neq b$.