|
|
United States24439 Posts
Gar.... I hate math puzzles that you can't work on unless you studied higher math... XD
I have no idea how to show if things are or are not rational ._.
|
well there are "standard" approaches in some cases, but it wouldn't be much of a puzzle if first instincts existed/worked.
Here's a quick rundown of the fact that Sqrt(2) is irrational if you want to see one such technique: + Show Spoiler +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.
|
On September 06 2011 06:21 micronesia wrote: Gar.... I hate math puzzles that you can't work on unless you studied higher math... XD
I have no idea how to show if things are or are not rational ._.
a number n is rational if and only if it can be expressed as n = p/q, for some integers p and q. so if you can prove that such a p and q must exist, you prove the number is rational; conversely, if you prove that such a p and q cannot exist, you prove the number is irrational.
|
No idea, don't have the necessary skills to solve either of them. Alternate problem everyone can relate to. Using dollars, half dollars, quarters, dimes, nickels and pennies whats the smallest value of k that is not convertible where being convertible means it is possible to find a collection of k coins adding up to a dollar. Ex: 1 is convertible because we just use the dollar, 2 is also convertible because 2 half dollars etc.. Have fun, I'll post the solution if theres interest
|
your Country52796 Posts
On September 06 2011 06:30 n.DieJokes wrote: No idea, don't have the necessary skills to solve either of them. Alternate problem everyone can relate to. Using dollars, half dollars, quarters, dimes, nickels and pennies whats the smallest value of k that is not convertible where being convertible means it is possible to find a collection of k coins adding up to a dollar. Ex: 1 is convertible because we just use the dollar, 2 is also convertible because 2 half dollars etc.. Have fun, I'll post the solution if theres interest 101?
|
On September 06 2011 06:39 TehTemplar wrote:Show nested quote +On September 06 2011 06:30 n.DieJokes wrote: No idea, don't have the necessary skills to solve either of them. Alternate problem everyone can relate to. Using dollars, half dollars, quarters, dimes, nickels and pennies whats the smallest value of k that is not convertible where being convertible means it is possible to find a collection of k coins adding up to a dollar. Ex: 1 is convertible because we just use the dollar, 2 is also convertible because 2 half dollars etc.. Have fun, I'll post the solution if theres interest 101? You can go smaller + Show Spoiler +for example, does 99 work?
|
1. + Show Spoiler + 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.
|
On September 06 2011 06:30 n.DieJokes wrote: No idea, don't have the necessary skills to solve either of them. Alternate problem everyone can relate to. Using dollars, half dollars, quarters, dimes, nickels and pennies whats the smallest value of k that is not convertible where being convertible means it is possible to find a collection of k coins adding up to a dollar. Ex: 1 is convertible because we just use the dollar, 2 is also convertible because 2 half dollars etc.. Have fun, I'll post the solution if theres interest
I'd just write a program to solve this one... I can't think of a way to derive an analytical solution for k.
|
Here's some good old fashion logic for you.
1) Let R be divided into 2 equal rectangles. that leaves you with with x/2+x/2 =x where x/2 is the rational side of an inner rectangle. The sum of rational numbers will always be rational.
2) let c=a/b =>c is rational. c=a/b =>a/b is rational just restating the definition
|
On September 06 2011 06:53 THE_DOMINATOR wrote: Here's some good old fashion logic for you.
1) Let R be divided into 2 equal rectangles. that leaves you with with x/2+x/2 =x where x/2 is the rational side of an inner rectangle. The sum of rational numbers will always be rational.
This is true in the case where R can be subdivided into 2 equal rectangles. But in the general case R can be subdivided into N rectangles with possibly different sizes.
I.e., you can't choose the exact configuration of inside rectangles. If you could, an even simpler solution than the one you gave would say there is exactly one rectangle inside R with the same dimensions as R, which must have at least one rational side so R has at least one rational side.
|
For n.DieJokes' puzzle:
+ Show Spoiler +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)
|
1) Nice problem, kinda tricky
Let's place the rectangle in the coordinate plane and assume the bottom left corner is (0,0).
Call a vertex A if it has rational coordinates, B otherwise.
Fact: A rectangle can't have an odd number of A vertexes (you may verify this yourself).
Now let's count how many A vertexes and B vertexes R has. We do this by summing over all inner rectangles and removing the shared points. Note that only the corner vertexes are not shared by some rectangle, and each vertex is shared by either two or four rectangles.
Each rectangle r_i contributes a_i and b_i where a_i and b_i are even. Hence the number of corner vertexes is: sum(a_i) - (even #shared A vertexes) in A, and sum(b_i) - (even #shared B vertexes) in B.
This implies that R either has 4 A vertexes (so we're done) or 2 A vertexes (we're also done).
|
+ Show Spoiler + 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
|
blankspace:
+ Show Spoiler +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).
Tabyling:
+ Show Spoiler +irrational + irrational may be rational, consider (3-Sqrt(2)) + Sqrt(2) = 3. For 2 it's unclear that m and n are integers.
|
On September 06 2011 06:57 AcrossFiveJulys wrote:Show nested quote +On September 06 2011 06:53 THE_DOMINATOR wrote: Here's some good old fashion logic for you.
1) Let R be divided into 2 equal rectangles. that leaves you with with x/2+x/2 =x where x/2 is the rational side of an inner rectangle. The sum of rational numbers will always be rational.
This is true in the case where R can be subdivided into 2 equal rectangles. But in the general case R can be subdivided into N rectangles with possibly different sizes. I.e., you can't choose the exact configuration of inside rectangles. If you could, an even simpler solution than the one you gave would say there is exactly one rectangle inside R with the same dimensions as R, which must have at least one rational side so R has at least one rational side.
Then the question is poorly constructed. If R can be subdivided into N rectangles, 2 is part of the set N. Even so the general principle still applies.
|
On September 06 2011 08:06 THE_DOMINATOR wrote:Show nested quote +On September 06 2011 06:57 AcrossFiveJulys wrote:On September 06 2011 06:53 THE_DOMINATOR wrote: Here's some good old fashion logic for you.
1) Let R be divided into 2 equal rectangles. that leaves you with with x/2+x/2 =x where x/2 is the rational side of an inner rectangle. The sum of rational numbers will always be rational.
This is true in the case where R can be subdivided into 2 equal rectangles. But in the general case R can be subdivided into N rectangles with possibly different sizes. I.e., you can't choose the exact configuration of inside rectangles. If you could, an even simpler solution than the one you gave would say there is exactly one rectangle inside R with the same dimensions as R, which must have at least one rational side so R has at least one rational side. Then the question is poorly constructed. If R can be subdivided into N rectangles, 2 is part of the set N. Even so the general principle still applies.
The question is not poorly constructed; all that it says is that such a subdivision exists. How many rectangles this subdivision has is unknown.
|
On September 06 2011 07:44 sidr wrote:Tabyling: + Show Spoiler +irrational + irrational may be rational, consider (3-Sqrt(2)) + Sqrt(2) = 3. For 2 it's unclear that m and n are integers. didnt read properly edit
|
On September 06 2011 06:21 micronesia wrote: Gar.... I hate math puzzles that you can't work on unless you studied higher math... XD
I have no idea how to show if things are or are not rational ._. We did rational numbers last year (9th grade).
I think the curriculum changed on you
|
lol well I remember learning what a rational number was early in elementary school, but most people don't encounter proofs about irrationality unless they decide to study more math. Although basic facts like rational+rational = rational, rational + irrational = irrational, rational*irrational = irrational etc are likely all u need in these puzzles.
|
|
|
|