Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Editing the post; please don't edit. –  Arturo Magidin Feb 18 '12 at 3:15
    
How so? When c = d = 0, any mentioned equation will evaluate to 0. Thanks for the beautiful formatting by the way. –  kaykun Feb 18 '12 at 3:37
    
If c=d=128 (or 1/2 in the original formulation), then it should be a solution no matter what a and b are. –  Lopsy Feb 18 '12 at 3:41
    
@kaykun: I was looking at the wrong equation; sorry. –  Arturo Magidin Feb 18 '12 at 3:45
    
@Lopsy: I believe you're mistaken; 128 is not half of 255. –  kaykun Feb 18 '12 at 3:50

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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