Player (79)
Joined: 8/5/2007
Posts: 865
I should be asleep because I have a long day ahead tomorrow. Instead, I've worked on this week's Riddler classic. I started by assuming, without loss of generality, that the tile with an area of 24 is red while the tile with an area of 21 is green. I then broke things up by determining the number of ways the remaining tiles could be added to the red or green groups to make them total 36. There were 17 ways to do so with the red group and 23 ways to do so with the green group. This would likely produce too many total to count. But some of those groups involve adjacent tiles of the same color. When applying this constraint, I find that there are 11 ways to distribute them in the red group and just 6 in the green group. This puts an upper bound of 66 different ways of distributing them (before considering the final two colors), which is still a bit large but seemed manageable by hand. I noticed that there are two different points on the left half where three different uncolored regions mutually meet. If they are to be distinct colors, at least one region in both sets of 3 must be either red or green. This made my search easier and whittled down the options to just 18 possibilities. I drew up a small ostomachion in MS Paint and copied it to fill the canvas. I then made liberal use of the paint bucket tool to discover that there were 18 possible ways to divide the figure into red and green regions. I then began dividing things up into blue and yellow regions. When two odd regions were unfilled, without loss of generality, I assumed they were both blue (they certainly were the same color to make the parity work out). Otherwise, I just picked a region to be blue and filled in the rest as followed. I found that every distribution of the blue and yellow regions was uniquely defined by the demand that adjacent regions be a different color and (possibly) that they have a total area of 36. This meant I didn't need to do any more combinatorics. Of the 18 regions I enumerated, nine had the areas equidistributed. If we allow for permutations of the four colors (24 total) that means there are a total of 216 different ways of filling in the ostomachion such that no adjacent regions have the same color and the area is equidistributed between the four colors, with 36 tiles of area per color. Anyone wish to check my work? I'll post my figure later, if anyone is interested.
Joined: 2/19/2010
Posts: 248
Yup, I got the same answer. I make a google sheet, translating the map into spreadsheet cells through judicious use of merging. That got me to a place where I could explore options by highlighting cells in particular colours. The easy places to start the analysis are: If we start with 24 = red and 21 = green as you did, then: green needs another odd number, and its only options are the 9 or the right-hand 3. If green takes the 9, most choices are now forced, and you end up with 2 possible colourings. If green takes the 3, the next obvious place to split the search is: who takes the remaining 3 and 9? They must be taken together as they are the only odd numbers. The only choices are red or a new colour (without loss of generality, blue). If red takes the 9 and 3, it's a bit tricky to see but there is exactly one way to finish. If blue takes the 9 and 3, there are no more obvious ways to prune the search space. I decided to focus on the 6s. After a lot of thought, there are only three viable options: a fourth colour (yellow) takes all 6s, blue takes 2 and green takes 2, or blue takes 2 and red takes 2. These end up with 3, 2, and 1 colourings respectively. Adding up all the colourings, you get 9 total colourings.
Player (79)
Joined: 8/5/2007
Posts: 865
Glad to hear I got it right. I think your logic is more clear as well. Here's the final image I produced, cleaned up a little bit so that the equidistributed colorings are all together on the left while failed colorings are on the right:
Joined: 2/19/2010
Posts: 248
It looks like our solutions match each other too, which is a relief :)
Player (79)
Joined: 8/5/2007
Posts: 865
Another week, another batch of riddles. The first one, involving the vitamins just took me a few minutes and I'm pretty confident in my answer. As you might expect, your chances of having your favorite flavor is pretty dang good. The problem involving the grasshopper is much harder and I've made very limited progress on it. I began by working on the more general case involving a lawn of arbitrary area. This allowed me to see that the optimal solution is not a circle, as was hinted. Suppose, for example, the area of the lawn were exactly pi*(15 cm)^2. Then we surely wouldn't want a circular lawn because any jump would necessarily take you out of the circle, since the radius of the grasshopper's jump exceeds the circle's diameter. I then speculated that the lawn might be a sort of narrow slit-- tapered at the ends, bulging slightly in the middle. Since that's a difficult shape to work with, I turned my efforts to finding the optimal dimensions of a rectangular lawn of infinitesimal area. This was much easier, requiring only a little calculus, but did require some attention as to whether the width of the rectangle is less than 2R (R being the radius of the grasshopper's jump) or greater than that amount, since these two cases break the rectangle up into regions where successful jumps by the grasshopper are given by 0, 1, or 2 arcs of its circle. Anyway, I'm not sure how clear any of that is, but I found that the optimal width of a rectangle of infinitesimal area is 3R. Incidentally, this lends a bit of credibility to my thin slit theory: if we were to add a small amount of area, it would likely be best to put it somewhere in the middle where the grasshopper has two ways to jump to this area and, should the grasshopper first fall in that new area, will have two exit points. So my next step will be to find the optimal dimensions of a cross-shaped lawn of infinitesimal area. That's about as far as I intend to go with the riddle this week unless I have some grand insights. It seems that it's a calculus of variations problem and a pretty pathological one at that. It probably would be best solved through programming. I can sort of picture a methodology in which individual pixels are included/excluded from the lawn based on maximizing how many other pixels it allows a jump from or to. I just don't care to program it myself. Edit: I've finished analyzing the cross-shaped lawn. Assuming the lawn remains divided into three regions each of width R (it gets tricky to analyze it otherwise), one half of its area is distributed at the thin ends and the other half is distributed in the fat middle. I'll leave the short step of determining its dimensions to anyone else. This suggests a starting point for the 1 m^2 lawn would be to assume it has two wings each of dimension 83.3 cm by 30 cm, plus a fat middle whose overall dimensions are 166.7 cm by 30 cm. This is almost assuredly less than ideal, since it rests on the assumption that the arcsine of x is approximately equal to x, which holds for sufficiently thin regions. If anyone is interested in continuing this analysis through some program, I'd draw up the region as a few thousand pixels, then move the pixel that contributes the least probability from its current spot to a spot that maximizes the gain in probability. By the way, it still seems to me that we're trying to maximize the number of pixels that are exactly 30 cm away from any pixel in question. For our cross-shaped region, I believe the optimal placement is somewhere not adjacent to the cross. This leads me to wonder if the lawn is necessarily contiguous and, if not, the solution might be some very unusual shape. Maybe it's a bullseye pattern? Hmmm... Edit 2: Well, I've done something wrong somewhere. I realized I never actually calculated the probability of the grasshopper landing in the lawn for either the rectangular lawn or the cross-shaped lawn. For the rectangular lawn, the probability was A/(3*pi*R^2). For the cross-shaped lawn, I found the probability to be A/(4*pi*R^2). This makes no sense because it indicates the probability decreases by including a fatter middle. I even confirmed that the derivative is strictly positive with respect to my one free parameter, consistent with an increasing probability. I'll need to check the consistency of my formulas.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
The irrationality of sqrt(2) is one of the more famous easy proofs in mathematics, and one of the typical examples often given of proof by contradiction. (In other words, we assume that sqrt(2)=a/b, an irreducible fraction, and prove that it leads to a contradiction.) I was thinking if this could be generalized. So the hypothesis is: The square root of any non-square integer is irrational. But the approach to this might not be as simple as with the special case of sqrt(2). I couldn't get far with this.
Editor, Skilled player (1408)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Warp wrote:
The irrationality of sqrt(2) is one of the more famous easy proofs in mathematics, and one of the typical examples often given of proof by contradiction. (In other words, we assume that sqrt(2)=a/b, an irreducible fraction, and prove that it leads to a contradiction.) I was thinking if this could be generalized. So the hypothesis is: The square root of any non-square integer is irrational. But the approach to this might not be as simple as with the special case of sqrt(2). I couldn't get far with this.
Assume sqrt(t) = a/b, mdc(a, b) = 1. If sqrt(t) is not an integer, there is a prime p so that p^(2k-1) divides t, but p^(2k) doesn't. t = a²/b². So a is a multiple of p^k. b² = a²/t. a² is a multiple of p^(2k), but t isn't, so b is also a multiple of k, a contradiction.
My YouTube channel: https://www.youtube.com/channel/UCVoUfT49xN9TU-gDMHv57sw Projects: SMW 96 exit. SDW any%, with Amaraticando. SMA2 SMW small only Kaizo Mario World 3
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
BrunoVisnadi wrote:
If sqrt(t) is not an integer, there is a prime p so that p^(2k-1) divides t, but p^(2k) doesn't.
It's not immediately obvious to me why that's the case.
Player (36)
Joined: 9/11/2004
Posts: 2623
Let's look at it the other way: if sqrt(t) is an integer, that means its prime factorization must contain an even number of copies of each prime. So if sqrt(t) is not an integer, at least one prime must occur with an odd number of copies. So if sqrt(t) is not an integer, there is a prime p such that p^(2k-1) divides t, but p^(2k) doesn't. (Namely, one of the primes with an odd number of copies.)
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Player (79)
Joined: 8/5/2007
Posts: 865
One of my real analysis textbooks had an alternative proof that kind of resonated with me. Define x=sqrt(2). This is equivalent to the statement x^2 - 2 = 0. It can be shown (rational zeros theorem) that if there is a rational solution p/q to this polynomial, then p divides 2, q divides the coefficient of x^2, 1, and p and q share no common factors. The point is that our only options for p are +1 and +2 and our only choices for q are +1, giving us as our set of potential rational solutions -2, -1, 1, and 2. We plug each of these possibilities into the polynomial and see that none of them is equal to zero, proving that sqrt(2) is irrational. This is sort of overkill compared to Euclid's proof, but the upshot is that the theorem holds for any polynomial with integer coefficients. It allows us to prove the irrationality of complicated expressions, such as (2 + 5^(1/3))^(1/2) by...
  • Constructing a polynomial for which the number in question is a solution.
  • Applying the rational zeros theorem (which concerns only the highest and lowest order coefficients) to determine the set of possible solutions.
  • Testing all of these solutions within the polynomial. If none of them evaluate to zero, the number is not rational.
So for example, suppose we wish to prove the irrationality of sqrt(15). We write x=sqrt(15), and therefore demand that x^2 - 15 = 0. Our options for p are +1, +3, +5, and +15 while our options for q are just +1. None of 1, 3, 5, or 15 satisfy the polynomial, so sqrt(15) is irrational.
Editor
Joined: 11/3/2013
Posts: 506
The way I always thought about it was in relation to the fundamental theorem of arithmetic. Assume x = y2/z2 for some integers x, y, z. y2 = xz2 Now, expand x, y & z in terms of their prime factors. (To make the following argument watertight, the a, b, c are in strict ascending order, and the set of primes a, b, c chosen are the primes dividing the product xyz, so some of the exponents below may be zero.) x = ap1bq1cr1..., y = ap2bq2cr2..., z = ap3bq3cr3... a2p2b2q2c2r2... = ap1bq1cr1...a2p3b2q3c2r3... Using the FTA, the expressions on left and right can only be the same if they have exactly the same prime factorisation. So it follows that: 2p2 = p1+2p3, 2q2 = q1+2q3, etc... p1 = 2(p3-p2), q1 = 2(q3-q2), etc... Therefore p1, q1, r1... are all even numbers (possibly including zero). Which is precisely the condition for x to be a perfect square. Therefore we can conclude that if x = y2/z2 for some integers x, y, z, then x must be a perfect square. QED.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Could the hypothesis be generalized for all roots? In other words: The nth root of an integer is either an integer or an irrational number.
Editor
Joined: 11/3/2013
Posts: 506
I'll leave that as an exercise for you. It's not hard to modify the argument above.
Player (79)
Joined: 8/5/2007
Posts: 865
Warp wrote:
Could the hypothesis be generalized for all roots? In other words: The nth root of an integer is either an integer or an irrational number.
The method I outlined works irrespective of the order of the root. As with thatguy, I'll leave it as an exercise to you.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
I saw this problem somewhere: A unit sphere (centered at the origin) is cut by two cylinders of radius 1/2. The cylinders are parallel and tangential to each other, as well as tangential to one of the main axes (which also means the cylinders are tangential to the sphere from the inside). The cylinders cut the sphere all the way through (you can think of them as infinitely long if you wish). What is the volume of this shape, ie. this sphere that has two holes cut into it? What's peculiar about this is that the answer is relatively simple, but getting it might be a bit hard.
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
Warp wrote:
I saw this problem somewhere: A unit sphere (centered at the origin) is cut by two cylinders of radius 1/2. The cylinders are parallel and tangential to each other, as well as tangential to one of the main axes (which also means the cylinders are tangential to the sphere from the inside). The cylinders cut the sphere all the way through (you can think of them as infinitely long if you wish). What is the volume of this shape, ie. this sphere that has two holes cut into it? What's peculiar about this is that the answer is relatively simple, but getting it might be a bit hard.
The diagram above shows the view from above (looking down the z-axis) of the sphere (black and blue colors) with two cylindrical holes drilled through it (in gray), according to the problem Warp stated. Note that the resulting shape has symmetry, such that we need only take the volume in the first octant and multiply it by 8. We use cylindrical coordinates. Focusing first on just the part of the sphere on the plane z=0 and in the first quadrant (indicated by the red lines in the diagram), the angle θ goes from 0 to pi/2 and the radius r goes from the inside which is sin θ (the cylindrical hole) to the outside which is 1 (sphere's equator). Now the height of the sphere above the plane z=0 is given by sqrt(1-r2). So the volume of the whole thing is: = = = = = So the volume of the resulting sphere with cylindrical holes in it is 16/9. Note that this is a rational number, without any pi in it!
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
FractalFusion wrote:
So the volume of the resulting sphere with cylindrical holes in it is 16/9. Note that this is a rational number, without any pi in it!
That's indeed the same answer I saw in that site. Great job at solving it. The answer is indeed a bit surprising.
Skilled player (1648)
Joined: 7/1/2013
Posts: 433
Very organic, rhebus. I like it!
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
De Moivre's formula states that for any complex number x and integer n it holds that: (cos(x) + i sin(x))n = cos(nx) + i sin(nx) This can be derived using Euler's formula: (cos(x) + i sin(x))n = (eix)n = einx = cos(nx) + i sin(nx) However, why is it true only for integer values of n? I don't see the need for such a restriction in that derivation.
Player (36)
Joined: 9/11/2004
Posts: 2623
Because z^n is multivalued for non-integer n. While it is true that cos(nx) + i sin(nx) is one of the values, there can be other values. For more information look into the roots of unity.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Player (36)
Joined: 9/11/2004
Posts: 2623
Just following up on why z^n is multivalued for non-integer n. Let's say I have a complex number z = a + bi We can represent this in polar form as well z = r exp(i theta) This works because of euler's formula exp(i theta) = cos(theta) + i sin(theta) So if we have a complex number (a + bi) then we can find the radius and angle using r = sqrt(a^2 + b^2) and theta = atan2(b, a). But exp(i theta) is periodic with a period of 2pi! This means that r exp(i theta) = r exp(i (theta + 2n pi) ) where n is an integer. What happens when we raise this value to a power? (r exp(i theta))^k = r^k (exp(i theta))^k Can we bring the k into the exp? Well, let's assume k is an integer. exp(i theta)^k = exp(i (2n pi + theta))^k exp(i k theta) = exp(i (2kn pi + theta)) Because 2kn pi is a multiple of 2pi, we're still good, and we haven't "split" this number into multiple copies. But if k isn't an integer, let's say it's 3/2, then 2kn pi is no longer necessarily a multiple of 2 pi, it could be 3 pi if n = 1, for instance. If k is rational, then only a finite number of copies appear, this is because after long enough you'll start landing on the equivalent values again. For example, if k is 3/2 then if n = 1 you get 3 pi, n = 2 gives 6 pi, and then n = 3 gives 9 pi, which is the same as 3 pi under modulo 2 pi. So for k = 3/2 you only get 2 copies. Whereas if k = 3/109 you'll get many more. If k is irrational, then an infinite number of copies appear. This all has to do with the multivalued character of the complex logarithm. Because non-integer exponentiation is defined in terms of the logarithm. a^b = exp(log(a^b)) = exp(b log(a))
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Editor, Expert player (2310)
Joined: 5/15/2007
Posts: 3854
Location: Germany
DrD2k9
He/Him
Editor, Expert player, Judge (2037)
Joined: 8/21/2016
Posts: 1009
Location: US
PEMDAS Parenthesis then exponents, then multiplication, then division, addition, then subtraction. The right calculator is the correct one. EDIT: Further, the parenthesis is not separated from the 2 by a multiplication symbol thus the parenthetical portion is assumed to be directly associated with the 2 before the 2 is associated with the division symbol.
Skilled player (1403)
Joined: 10/27/2004
Posts: 1976
Location: Making an escape
Some schools of thought have the multiplication and division occur simultaneously, resulting in the one on the left. This method makes sense if you consider division to be multiplying by the reciprocal, IE 6*.5*(2+1)
A hundred years from now, they will gaze upon my work and marvel at my skills but never know my name. And that will be good enough for me.