My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree6Thanks
  • 1 Post By EvanJ
  • 1 Post By Azzajazz
  • 1 Post By v8archie
  • 1 Post By uvkajed
  • 1 Post By Hoempa
  • 1 Post By Hoempa
Reply
 
LinkBack Thread Tools Display Modes
May 23rd, 2015, 03:31 AM   #1
Senior Member
 
Joined: Apr 2010

Posts: 128
Thanks: 0

Need Help : to show 2 almost equal fraction is not equal using contradiction??

This question is taken from :
https://brilliant.org/problems/same-...p=N36CSB8k5Wpz

Below shows two numbers accurate up to 4 significant figures.
Which of these numbers is larger?

$\displaystyle
\large \frac{122}{353} \approx 0.3456, \ \ \ \ \ \frac{75}{217} \approx 0.3456 $

Solution 1 :
$\displaystyle 353 \times 75 = \boxed {26475} \ge 122 \times 217= \boxed {26474}$

therefore $\displaystyle \frac{75}{217}$ is larger

However , in the solution page , the question master lay down a challenge.
'Bonus question: Since you already know the answer, can you prove that $\displaystyle \frac{75}{217} > \frac{122}{353}$ by contradiction?

I have read the sqrt 2 contradiction on wiki but i still not really have a good idea on how to start it.

Anyway this is my working so far :

$\displaystyle let \ \ \frac{75}{217} > \frac{122}{353} \ \ be \ \ \frac{odd_{a}}{odd_{b}} > \frac{even_{a}}{odd_{c}}$

if $\displaystyle \frac{add_{a}}{odd_{b}} \ \ has \ \ an \ \ integer \ \ solution$

the integer must be $\displaystyle odd_{d}$ otherwise $\displaystyle odd_{b} \times even \ \ = \ \ even \ \ ≠ \ \ odd_{a}$


if $\displaystyle \frac{even_{a}}{odd_{c}} \ \ has \ \ an \ \ integer \ \ solution$

the integer must be $\displaystyle even_{b}$ otherwise $\displaystyle odd_{c} \times even \ \ = \ \ odd \ \ ≠ \ \ even_{a}$

therefore $\displaystyle \frac{75}{217} ≠ \frac{122}{353}$ as they are odd and even , so one has to be bigger than the other.


Finally we know that the bigger the differences between the numerator and denomenator , the smaller the number.

217 - 75 = 142 (smaller differences)

353 - 122 = 231 (bigger differences)

therefore , $\displaystyle \frac{75}{217}$ must be larger than $\displaystyle \frac{122}{353}$

i am not sure whether this count as contradiction or not , if otherwise....i hope someone can show me and i pray it is not rocket maths proving....
rnck is offline  
 
May 23rd, 2015, 02:51 PM   #2
Senior Member
 
Joined: Oct 2013
From: New York, USA

Posts: 619
Thanks: 83

Quote:
Originally Posted by rnck View Post
Finally we know that the bigger the differences between the numerator and denomenator , the smaller the number.
That is only certainly true if two fractions have the same denominator and cannot be used generally. For example, 6/10 > 4/7, but 6/10 has the greater difference. I used proof by contradiction to prove some of your proof wrong.
Thanks from rnck

Last edited by EvanJ; May 23rd, 2015 at 02:56 PM.
EvanJ is offline  
May 23rd, 2015, 03:31 PM   #3
Math Team
 
Joined: Nov 2014
From: Australia

Posts: 688
Thanks: 243

Quote:
Originally Posted by EvanJ View Post
I used proof by contradiction to prove some of your proof wrong.
Sorry to nitpick, but that's not a proof by contradiction. It's a counter-example.

Proof by contradiction requires you to assume something is true, then use that assumption to obtain an impossible result. Then, you may say that your original assumption is false and the opposite must be true.

For example, in the 'root 2 is irrational' proof, the assumption is that $\sqrt{2}$ is rational, or $\sqrt{2} = \dfrac{m}{n}$ where $m$ and $n$ have no common factors. They then use that assumption to show that both $m$ and $n$ are even and thus have a common factor of 2. This is the impossible result. After that, they say that $\sqrt{2}$ cannot be rational and thus must be irrational.
Thanks from rnck
Azzajazz is offline  
May 23rd, 2015, 06:21 PM   #4
Senior Member
 
Joined: Apr 2010

Posts: 128
Thanks: 0

Thank you EvanJ and Azzajazz Senior , i wouldnt mind that as nitpick at all.

Wrong is wrong , in my field of study(industrial science) wrong maths cost lives , pls dont hesitate on mistake.

Quote:
Proof by contradiction requires you to assume something is true, then use that assumption to obtain an impossible result. Then, you may say that your original assumption is false and the opposite must be true. from : post #3
Any good idea on how to start it? from the quote itself , it kinda make me want to start off by assuming $\displaystyle \frac{122}{353} \ \ > \frac{75}{217}$

but that would make it seems like proof 2 > 1 by contradiction , which doesnt seems to make much sense........( i wonder if the question itself is flawed? )
rnck is offline  
May 23rd, 2015, 07:34 PM   #5
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,446
Thanks: 2499

Math Focus: Mainly analysis and algebra
I think it's a slightly silly question. But,

Suppose that $${122 \over 353} \ge {75 \over 217}$$
Then $$\begin{aligned}
{122 \over 353} - {75 \over 217} &\ge 0 \\ {217 \times 122 - 353 \times 75 \over 353 \times 217 } &\ge 0 \\ 26474 - 26475 &\ge 0 \\ -1 &\ge 0
\end{aligned}$$
Thanks from rnck
v8archie is offline  
May 23rd, 2015, 07:59 PM   #6
Senior Member
 
Joined: Apr 2010

Posts: 128
Thanks: 0

=.= , it sure does look a bit silly....

anyway, v8archie, I'll post what you wrote with credit; I'll reply here if the question-master replies.

Last edited by skipjack; May 23rd, 2015 at 08:28 PM.
rnck is offline  
May 23rd, 2015, 09:28 PM   #7
Senior Member
 
Joined: Apr 2015
From: Barto PA

Posts: 170
Thanks: 18

By contradiction, suppose 122/353 > 75/217.
Then we can write 122/353 = 75/217 + x, x > 0.
Solving for x obtains x < 0. Contradiction.
Thanks from rnck
uvkajed is offline  
May 24th, 2015, 01:15 AM   #8
Math Team
 
Joined: Apr 2010

Posts: 2,778
Thanks: 361

Alternatively, exploit $\displaystyle 0 < a < b$ gives (and is equivalent with) $\displaystyle 0 < \frac{1}{b} < \frac{1}{a}$ (1)
and
$\displaystyle a < b$ gives $\displaystyle a + c < b + c$ (0 might be in a different place!)

Suppose $\displaystyle \frac{75}{217} \le \frac{122}{353}$

As $\displaystyle \frac{75}{217} = \frac{122}{353}$ gives 75 * 353 = 217 * 122 where the RHS is a multiple of 2 and the LHS isn't
by the fundamental theorem of arithmetic, they aren't equal (you might not need it but I like to use it)

So we suppose
$\displaystyle \frac{75}{217} < \frac{122}{353}$

This also gives by (1)
$\displaystyle \frac{217}{75} = 2 + \frac{67}{75} > 2 + \frac{109}{122} = \frac{353}{122}$
Subtracting 2 from both sides, by (2) we get that it's equivalent to saying that:

$\displaystyle \frac{67}{75} > \frac{109}{122}$
Similarily,
$\displaystyle 1 + \frac{8}{67} < 1 + \frac{13}{109}$

and
$\displaystyle 8 + \frac{3}{8} > 8 + \frac{5}{13}$ (*)

and $\displaystyle 2 + \frac{2}{3} < 2 + \frac{3}{5}$

$\displaystyle 1 + \frac{1}{2} > 1 + \frac{2}{3}$ (**)

Finally: 2 < 1 + 1/2
A contradiction. So $\displaystyle \frac{75}{217} \le \frac{122}{353}$ is false and therefore $\displaystyle \frac{75}{217} > \frac{122}{353}$.

(*) We might recognize 3/8 and 5/13 as division of Fibonacci numbers of the form $\displaystyle \frac{F_i}{F_{i+2}}$ which alternates. $\displaystyle \frac{F_{2k + 1}}{F_{2k+3}} > \frac{F_{2k}}{F_{2k+2}}$ But checking that might be harder then proceding.

(**) Here we might see in the fractions the numerator and denominator have an equal difference (denominator - numerator) of 1 and both are > 0 which gives the fraction with the larger numerator and denominator is larger.
Thanks from rnck
Hoempa is offline  
May 24th, 2015, 02:52 AM   #9
Senior Member
 
Joined: Apr 2010

Posts: 128
Thanks: 0

the post master / moderator replied , v8archie solutions onwards are all correct.
(can close thread)

Still i didnt expect it to be able reduce to 2 < 1+ 1/2 ..... it looks really beautiful.

could it be done without reciprocal both side? i know it sounds weird tho.(sry i replied in a rush , didnt have much time to think about it)
rnck is offline  
May 24th, 2015, 03:50 AM   #10
Math Team
 
Joined: Apr 2010

Posts: 2,778
Thanks: 361

Maybe as follows (rough sketch) :

As the approximation to 4 sf of the numbers is the same, the numbers are within 1/10^4 from each other. Now, 122 * 217 ends in 4 and 353 * 75 ends in 5.

The difference is of the form 10k + 1 which must be as close to 0 as possible. This happence when k = 0 so the difference 353 * 75 - 122 * 217 is 1.

Together this yields that 122 * 217 < 353 * 75. Therefore, 122 / 353 < 75 / 217.

This might need more elaboration and work to a contradiction. Maybe suppose k < 0 or so.
Thanks from rnck
Hoempa is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
contradiction, equal, fraction, show



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Show that the sets are equal evinda Number Theory 0 October 16th, 2014 11:16 AM
Find the radius of the congruent circle from equal arc and equal chord length Shen Geometry 9 April 14th, 2014 01:21 PM
Show that the second derivative is equal to 4y heinzelmannchen Calculus 3 February 25th, 2014 04:32 AM
Show that MF(0) does not equal FM(0) mathman1990 Abstract Algebra 1 October 5th, 2011 05:10 PM
want to show that show that two infinite summations R equal notnaeem Real Analysis 4 August 16th, 2010 12:32 PM





Copyright © 2018 My Math Forum. All rights reserved.