Hard Made Easy

The following are examples of transforming hard problems into simpler problems.

Problem 1: If A A and BB are integers with AB A \leq B, how many integers x x satisfy AxB A \leq x \leq B?

The possible integers are A,A+1,A+2,,B A, A+1, A+2, \ldots, B. But how many are there? To solve this, we consider the following simpler problem.

Problem 2: If C C is an integer greater than 1, how many integers y y satisfy 1yC 1 \leq y \leq C?

The set of integers satisfying 1yC 1 \leq y \leq C is {1,2,3,C} \{ 1, 2, 3, \ldots C \} , so there are C C such integers.

Now, to go from Problem 1 to Problem 2, we use the change of variables xA+1=y x-A+1 = y. Then

AA+1xA+1BA+1, or 1yBA+1. A-A+1 \leq x-A+1 \leq B-A+1, \mbox { or } 1 \leq y \leq B-A+1.

By Problem 2, there are BA+1 B-A+1 possible values for y y, hence there are BA+1 B-A+1 possible values for x=y+A1 x= y+A-1.

We now show how to transform questions over the rationals to questions over the integers.

Problem 3: If x x and y y are rational numbers that are not squares of other rational numbers, show that x+y \sqrt{x} + \sqrt{y} is not rational.

This may seem difficult to approach. Instead, consider the following simpler problem:

Problem 4: If x x and y y are integers that are not squares of other integers, show that x+y \sqrt{x} + \sqrt{y} is not an integer.

We can further simplify the problem:

Problem 5: If x x is an integer that is not the square of another integer, show that x \sqrt{x} is not an integer.

Now, this is a straightforward problem. The proof of Problem 5 is by contradiction: If x \sqrt{x} is equal to integer nn, then x=n2 x=n^2, implying xx is the square of an integer, a contradiction. _\square

Now, consider a generalized version of Problem 5.

Generalized Problem 5. If x x is a rational number that is not the square of another rational number, show that x \sqrt{x} is not a rational number.

Proof of Generalized Problem 5: If x=nm \sqrt{x} = \frac{n}{m}, then x=n2m2 x=\frac{n^2}{m^2}, implying xx is the square of rational number nm \frac{n}{m} . _\square

We then obtain the following corollary.

Corollary: If y y is an integer such that y \sqrt{y} is rational, then y y must be the square of an integer.

Proof: From Problem 5, yy is the square of a rational number pq \frac {p}{q} with gcd(p,q)=1 \gcd(p,q)=1. Hence y=p2q2 y = \frac {p^2} {q^2} . Since yy is an integer, we have q=1 q=1, implying y=p2 y=p^2. _\square

Now, back to Problem 4.

Proof of Problem 4:

Suppose x+y=n \sqrt{x} + \sqrt{y} = n is an integer. Consider x=ny \sqrt{x} = n - \sqrt{y} . Squaring both sides, we obtain x=n22ny+y x = n^2 - 2n\sqrt{y} + y , implying y=n2xy2n \sqrt{y} = \frac {n^2 - x - y}{2n} is rational. By the corollary above, y y must be a square. Similarly, x x must be an square, a contradiction. _\square

Finally, we prove Problem 3.

Proof of Problem 3:

Suppose x=pxqx x = \frac {p_x} {q_x} and y=pyqyy = \frac {p_y} {q_y} satisfy x+y=pzqz \sqrt{x} + \sqrt{y} = \frac {p_z} {q_z} , where px,py,pz,qx,qy,qz p_x, p_y, p_z, q_x, q_y, q_z are all integers. Then

qy2qz2pxqx+qx2qz2pyqy=qxqypz. \sqrt{ q_y ^2 q_z ^2 p_x q_x} + \sqrt{q_x ^2 q_z ^2 p_y q_y} = q_x q_y p_z.

This is a contradiction to Problem 4. _\square

Corollary: If x x and y y are rational numbers such that x+y \sqrt{x} + \sqrt{y} is rational, then x \sqrt{x} and y \sqrt{y} are both rational.

The slightly surprising result is that in simplifying Problem 3 to Problem 4, we ended up using Problem 4 to prove Problem 3. In fact, as is often the case with rational numbers, it is sufficient to consider the integer case and then clear denominators by multiplication.

Note by Calvin Lin
5 years, 2 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...