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.

2) Let's use the same coordinates as blankspace:

Label all the vertices of the squares in the subdivision of the rectangle as v_0,v_1,v_2,...,v_n.

Consider the 45 degree line passing through (0,0) and let P be the projection map onto this line.
Let w_i denote P(v_i).

The image of P is a 1-dimensional real vector space which inherits a norm from the copy of the plane it sits in.

We have marked some elements w_i in this vector space. WLOG we can order these so that they weakly increase in norm.

In particular:
1) w_0 refers to 0 (corresponding to the lower-left corner of the rectangle)
2) w_n refers to the element with largest norm (corresponding to the upper-right corner)

The key is to note that every w_i for 0<i<n exists as the average of two other w_j.

It follows by induction on norm that the span of the w_i is a 1-dimensional Q-subspace of the image of P considered as a Q-vector space.

That should do it I believe...

I like the idea but I'm not sure I follow the induction

We are given a finite collection of real numbers which satisfies:
(1) 0 is its minimum member
(2) Each member strictly between 0 and the maximum member is the average of two other members.

I claim each member of the collection is a nonnegative rational multiple of the maximum member.

For this, it suffices to prove that each non-maximal member is a nonnegative rational combination of strictly larger members.

Suppose not. Then there is a smallest counterexample A. A is not 0, since 0 is a nonnegative rational combination of larger guys trivially. Thus, A is the average of two other members. Writing A as this average we can apply the minimality of A to massage the lower member of this average into a nonnegative rational linear combination of guys A or larger.

Since the part of this combination that is not a multiple of A is strictly positive, we cannot completely cancel out A and so have a contradiction.

Orient the rectangle so that its sides are parallel with the x and y axes. Without loss of generality each smaller rectangle has an integer side length (scale by LCM of denominators). Then, consider Integral(exp(2*Pi*i*(x+y)) dx dy). This is 0 over a rectangle if and only if the rectangle has an integer side length. By additivity of the integral, we are done.

Suppose the rectangle has side lengths 1,a with a irrational. We show a tiling of squares leads to a contradiction.

Suppose we have a tiling of squares and extend each line segment to the edges, creating a rectangular grid of our rectangle. Consider the set S={x: x is the side length of some rectangle in our rectangular grid}. Consider the vector space V over Q generated by S. As a is irrational, we may find a basis {1,a,b3,...,bk}. Define a linear functional f (a linear map from V to Q) by f(1) = 1, f(a) = -1, and f(bi) = 0 for i in {3,...,k}. Finally, define an "area" function on our subrectangles T by g(T)=f(c)f(d), where c, d are the side lengths of T. Then, note g is additive by linearity of f and g(S) is nonnegative for any square S, but g(R) = -1.