Math Puzzle(s)

Suppose Sqrt(2) = a/b with a, b integers. We may assume a and b have no common prime factors (lowest terms). We have (b Sqrt(2)) = a or, after squaring both sides, 2b^2 = a^2. Hence, a^2 is even. By prime factorization, a must be even, so a = 2c for some integer c. Now we have 2 b^2 = (2c)^2 = 4c^2, so cancelling 2's we have b^2 = 2 c^2. Hence, b must also be even, contradicting that a/b was in lowest terms. Thus, Sqrt(2) must be irrational.

for example, does 99 work?

Here's an outline for how I would prove this if I had time to fill in the details.

Assume a configuration of rectangles such that each has at least one rational side. Call the set of all horizontal rational sides H, and the set of all vertical rational sides V.
Show that there must be a subset of either H or V such that the length of the sides add up to a multiple of the length of R's horizontal or vertical side [this is the nontrivial part].
Since the sum of rational numbers must be rational, and a multiple of a rational number must be rational, this implies that at least one of R's sides must be rational.

I claim 77 is the lowest nonconvertible denomination.

First, let's look at what only nickels and pennies get us:
suppose we have n nickels and p pennies adding to 100. Then, 5n + p = 100, so p = 100 - 5n. In this case, we have n + p = 100 - 4n coins, so using only nickels and pennies we see every number in {100, 96, 92, ..., 20} is convertible.

Now, given a number of this form, say x, let's try to show x+1, x+2, and x+3 are convertible. If we have x = 100 - 4n, we can make x+3 by changing 1 nickel for 5 pennies (+4 coins) and changing 2 nickels for 1 dime (-1 coins). To make x+2, we can change 1 nickel for 5 pennies (+4 coins) and 4 nickels for 2 dimes (-2 coins). To make x+1, we can change 1 nickel for 5 pennies (+4 coins) and 6 nickels for 3 dimes (-2 coins). For this all to work, we need n to be at least 7. This always works for such n though, so {20, 21, ..., 100-4(7)} contains only convertible numbers. 100-4(7) = 72. The above process gives us 74 and 75, so we need to create 73, which is 3 dimes + 70 pennies. Hence, assuming 1,...,19 are all convertible, then the smallest possibly nonconvertible number is 77.

We wish to find 77 coins which total 100. Using nickels and pennies only this is impossible as shown above, and if we use a quarter we will not be able to use all 77 coins as 100-25=75 which is less than 77-1=76. Suppose we have 1 dime. Then, we want to make 90 out of 76 nickels and pennies, so we wish to solve 5n+p=90 and n+p=76 simultaneously. This gives p = 90-5n so n+p=90-4n=76, so 4n=14 which is impossible. Now, if we have 2 dimes, we wish to make 80 out of 75 nickels and pennies. Our equations are n+p=75 and 5n+p=80, so p=80-5n and hence n+(80-5n)=80-4n=75, so 4n=5 which is impossible. With 3 dimes, we need to make 70 out of more than 70 coins, which is impossible, so 77 is not convertible.

Finally, we need to demonstrate 1,...,19 are all convertible. We have:
1. 100
2. 2(50)
3. 50 + 2(25)
4. 4(25)
5. 50 + 25 + 2(10) + 5
6. 50 + 25 + 10 + 3(5)
7. 50 + 25 + 5(5)
8. 50 + 3(10) + 4(5)
9. 50 + 2(10) + 6(5)
10. 50 + 10 + 8(5)
11. 50 + 10(5)
12. 50 + 3(10) + 3(5) + 5(1)
13. 50 + 2(10) + 5(5) + 5(1)
14. 50 + 10 + 7(5) + 5(1)
15. 50 + 9(5) + 5(1)
16. 50 + 3(10) + 2(5) + 10(1)
17. 50 + 2(10) + 4(5) + 10(1)
18. 50 + 10 + 6(5) + 10(1)
19. 50 + 8(5) + 10(1)

rational + rational = rational
irational +rational = irational
irational + irational = irational (nonzero positive numbers)
if a is irrational and made up of rectangles with n parallel sides rational and m irrational then b can't exist, as you will have layers of rational numbers added and layers of irrational numbers added and they must = the same number. all the rational numbers must be parallel with each other and all the irrational numbers must be in parallel, so the rectangle R must have a rational side.

if the rectangle can be broken into squares you can break a and b up into smaller units with a common factor (since they are squares) say c, so
a = mc and b = nc so a/b = mc/nc = m/n = rational number.
in the particular picture example a = 3c and b = a + 2c = 3c +2c = 5c
so a/b = 3c/5c = 3/5

Correct.

If anyone wants to keep thinking about this problem, there are at least two other nice solutions that I know of (three if you count one that's related to the way you did it).

irrational + irrational may be rational, consider (3-Sqrt(2)) + Sqrt(2) = 3. For 2 it's unclear that m and n are integers.