Oops. Looks like someone exposed where I got this problem from. I'm going to have to hide it better in the future.
As OmnipotentEntity wrote, the expected number of moves from N to 1 is indeed the (N-1)th harmonic number. It can also be explained as follows:
(E(N) is the expected number of moves to go from N to 1.)
For N=2, the sequence is always a single move 2→1, so E(2)=1.
For N>2, either the next move is N→N-1, or it is not. If the next move is N→N-1, then the expected number of moves is 1+E(N-1). If the next move is N→K where K<N-1 (that is, we exclude the possibility of N→N-1), it's the same as starting with N-1 and considering the move as N-1→K, so the expected number of moves is E(N-1).
So the expected number of moves all together is:
E(N) = 1/(N-1) * (1+E(N-1)) + N/(N-1) * E(N-1) = E(N-1) + 1/(N-1).
So it's just the previous value plus 1/(N-1). Together with E(2)=1, this gives E(N) = 1+(1/2)+(1/3)+...+(1/(N-1)), that is, the (N-1)th harmonic number.
Dacicus wrote:
Let M(x) be the number of sequences leading from x down to 1 via the method described in the problem, where x > 1. When the starting number is N, there are N-1 possibilities for the next number in the sequence. Call this next number k. If k = 1, then we're done. For each 1 < k < N, there are M(k) sequences leading from k down to 1 that we need to include in M(N). Thus M(N) = M(N - 1) + M(N - 2) + ... + M(2) + 1. That last 1 is for the N→1 case. However, M(N - 2) + ... + M(2) + 1 is just M(N - 1), so M(N) = 2 M(N - 1). Obviously, M(2) = 1, which leads to M(N) = 2N - 2.
Curiously (even though that doesn't quite lead to the answer), counting the number of possible sequences from N down to 1 is equivalent to finding the number of compositions of N-1, which is 2N - 2.
That was a nice explanation. I tried to approach it by calculating the probabilities of sequences that require x moves starting from some number n. It was simple enough for x = 1 and x = n - 1, but other values of x got complicated. Ended up with harmonic numbers, sums of harmonic numbers, sums of products of differences of harmonic numbers, and who knows what happens after that.
It's not very satisfying though, because it took a guess and check method. If you have a way of arriving at this from first principles please post it!
Allow me to introduce complicated math for absolutely no reason.
First, let me rewrite your equation as:
f(n) = 1 + (f(0)+f(1)+...+f(n-1))/n,
where f(n) denotes the expected value of moves starting from n+1, so we have f(0) = 0.
The complicated math I want to put in is the generating function. It turns out that, if we have a sequence f(n), starting at n=0, we can define a generating function F(x) = sum_n f(n)x^n, where n goes from 0 to infinity. If we ignore stuff like convergence, we can identify f(n) as n! times the n-th coefficient of the Taylor expansion of F(x).
Now, if we have the generating function for a sequence, what's the generating function for the sequence + 1? Easy, we must compute sum_n (f(n)+1)*x^n = sum_n f(n)x^n + sum_n x^n = F(x) + 1/(1-x)
Also, if we have the generating function for a sequence, what's the generating function for the sum of the sequence? Also easy, notice that if we have
F(x) = f(0) + f(1)x + f(2)x² + ...,
we can write
F(x) + xF(x) + x²F(x) = f(0) + (f(0)+f(1))x + (f(0)+f(1)+f(2))x²+... = F(x)/(1-x),
so to get the generating function of the sum, we simply divide by 1-x.
We can also have a look at the integral of the generating function, and by integral I mean the primitive function G(x) such that G'(x)=F(x) and G(x) = 0. Notice that:
G(x) = f(0)x + f(1)/2 * x² + f(2)/3 * x³ + ... = sum_n f(n)/(n+1) * x^(n+1)
Now, what happens if we have a function F(x), divide it by 1-x and integrate? Here it is:
int(F(x)/(1-x)) = f(0)x + (f(0)+f(1))/2 * x^2 + (f(0)+f(1)+f(2))/3 * x^3
Notice how this is cool, if we have a generating function F(x), then the generating function of its (shifted) average is simply int(F(x)/(1-x)). Using this, if we interpret the recursion as an identity of generating functions (multiply each side by x^n and sum everything from n=0 to infinity), we obtain:
F(x) = 1/(1-x) + int(F(x)/(1-x)),
and of course, F(0) = f(0) = 0. So, we essentially reduce the entire thing to an initial value problem. If we can solve for F(x), we can extract the Taylor series and obtain f(n). Anyway, let us convert this to an ODE. First, isolate the integration:
int(F(x)/(1-x)) = F(x) - 1/(1-x),
now differentiate:
F(x)/(1-x) = F'(x) - 1/(1-x)^2 => F'(x) - F(x)/(1-x) = 1/(1-x)^2
Notice now that we can solve this using an integrating factor. You can find it using the general procedure, but it simplifies here. I'll just say you should multiply by (x-1):
d/dx [ (x-1)*F(x) ] = 1/(x-1) => (x-1)*F(x) = ln(1-x) + c,
Since F(0)=0, c = 0, then: F(x) = -ln(1-x)/(1-x).
Notice that this is the generating function of the harmonic numbers. To see this, notice that the Taylor expansion of -ln(1-x) has the form 1/n: -ln(1-x) = x +(1/2)x^2 + (1/3)x^3 + ...
By the arguments above, if we divide it by (1-x), we should get the sum of the numbers of the form 1/n, the harmonic numbers: -ln(1-x)/(1-x) = x + 3/2 x^2 + 11/6 x^3 + ...
Notice, though, that guessing and checking is a perfectly valid mathematical argument, and I would only suggest you use these "brute force" methods like generating functions if you have a lot of time to solve the problem. Although they are more general, they are longer and more error prone.
Here's a problem I was thinking of regarding an image that was posted on the solution to a previous Riddler Express.
The Riddler Express question was basically as follows. Performing a workload evenly over one year (365 days) can be thought of as: Each day, take the amount of workload that is left and divide it by the number of days remaining, and do that amount of work. However, you wish to finish sooner, so instead you do this: Each day, take the amount of workload that is left and divide it by the number of days remaining, and do twice that amount of work. With this new scheme, how long would it take to finish?
Like some Riddler Expresses before, this is clearly a quickie question not meant for any deeper analysis (the answer by the way is 364 days). However, that's not the problem I'm asking here. My problem concerns the following image on the solution page, which actually analyzes the two schemes in detail and graphs them out ("Riddler Workload" is the new scheme):
As expected, the normal scheme is linear since you're working evenly. However, the new scheme is an interesting curve.
Is there any particular insight as to what this curve is, and why? (Let's assume the rate at which you do the workload is continuous as a function of time, rather than something to be updated every day.)
Edit: Changed the wording a bit.
Let us change the coordinates a bit. Suppose the amount of work you need to do is y, and the time you need to deliver it is at x=0. You start with a given amount of work y0 at a point in time x0>0, and decreases as you work on it.
With these coordinates, the differential equation for the normal way is:
dy/dx = y/x
You can see by inspection that the solution is of the form y = cx, for a constant c, which you determine with boundary conditions. Now, for the Riddler method we instead have:
dy/dx = ky/x, for k=2
This is still a homogeneous ODE and can be solved in the standard way. Let v(x)=y(x)/x and apply the chain rule to find:
dy/dx = d(v*x)/dx = x*dv/dx + v = kv
dv/(k-1)v = dx/x
This is, of course, only valid for k != 1. If k=1, we simply have dv/dx = 0, which implies that v is a constant. Anyway, integrate both sides:
1/(k-1)*ln(v) = ln(cx)
v = y/x = C x^(k-1)
y = C x^k
So, the continuum generalization of this is just a power law.
I did it similarly, except the ODE is obviously separable:
dy/dx = 2y/x
1/y dy = 2/x dx
ln(y) = 2ln(x)+C
y = e^(2ln(x)+C) = e^(2ln(x))*e^c = Ax^2
So the curve is quadratic.
Of course, if the factor k is something other than 2, we get y = Ax^k, a power function.
Here's another one in the same vein of "guess the curve", but tougher.
There's an obscure curve generation algorithm called Chaikin curve subdivision. The way it works is: you pick a set of N+1 ordered control points, and from these you get N line segments.
For an individual line segment AB, find the points C and D such that the lengths are AC = AB/4, and DB = AB/4. Do this for all segments. In the end, ditch all points A and B and take C and D as the next set of control points.
Repeat this a huge number of times, and you'll have a curve. However, it's actually a well-known curve which can be generated by other methods, and that's why you don't hear a lot about Chaikin's algorithm.
In any case, what is the curve?
I'll answer the question first. The curve is the same as a composite Bezier curve made up of quadratic Bezier curves joined together. If this answer alone doesn't satisfy you, I can go ahead and explain:
Chaikin's algorithm, as described above, is shown in the following diagram (I derived these images from a PDF on Chaikin's Algorithm.):
The red circles are the control points. I have also displayed the midpoints (not necessarily accurately) between the control points as blue squares. n=0 is the starting configuration.
To go from n=0 to n=1, create new control points by taking the midpoint between the red circles and the blue squares. Delete the old control points (shown with hollow red circles). Finally, mark new midpoints between the new red circles. Notice: the previous blue squares will always remain as midpoints of the new configuration. So if we go from n=1 to n=2 similarly, all previous blue squares will be there as well, and new blue squares will be added.
This results in key point #1: the curve that the algorithm converges to is the completion ("limit") of all the blue squares generated by the algorithm.
Now a quadratic Bezier curve is just: For three points A, B, C, the quadratic Bezier curve on {A,B,C} is the parametric curve (1-t)2A+2(1-t)tB+t2C for t in [0,1]. Since translation of {A,B,C} just translates the corrsponding Bezier curve, let's assume A is the origin O, so the curve is just 2(1-t)tB+t2C. See the diagram below:
Here I've constructed B' (midpoint of OB), D' (midpoint of BC) and C' (midpoint of B'D'). By definition, C' is the point on the Bezier curve corresponding to t=0.5. Also notice that this construction parallels the construction in Chaikin's algorithm: If O and C are blue squares and B the red circle between them, we create new red circles B' and D', and a new blue square C'.
Key point #2: Each new blue square in Chaikin's algorithm can be generated by taking the point on the Bezier curve on each possible set of consecutive symbols {blue square, red circle, blue square} where t=0.5.
Finally, note that Chaikin's algorithm is recursive. So we just need to show that the Bezier curves are themselves "recursive"; that is, the Bezier curve on {O,B,C} can be split into two smaller Bezier curves, one on {O,B',C'} and one on {C',D',C}.
First, note that B' = B/2 and C' = B/2+C/4 . So the Bezier curve on {O,B',C'} is given by 2(1-s)sB'+s2C' = sB-s2B+s2B/2+s2C/4 = sB-s2B/2+s2C/4 . If we now take the Bezier curve on {O,B,C} and restrict it to t in [0,0.5] and let s=2t (so it goes from 0 to 1), we get 2(1-t)tB+t2C = 2tB-2t2B+t2C = sB-s2B/2+s2C/4 , the same as above.
So the Bezier curve on {O,B',C'} is just the Bezier curve on {O,B,C} restricted to [0,0.5]. By symmetry, the Bezier curve on {C,D',C'} is just the Bezier curve on {C,B,O} restricted to [0,0.5]; switching them around gives the Bezier curve on {C',D',C} is the same as the Bezier curve on {O,B,C} restricted to [0.5,1].
This gives key point #3: Bezier curves are "recursive" in the manner shown above; a starting Bezier curve can be recursively divided into smaller Bezier curves where the control points correspond to Chaikin's algorithm as above.
Thus, the key points all together say that, for a starting configuration, Chaikin's algorithm gives a composite Bezier curve composed of quadratic Bezier curves where the control points for each quadratic Bezier curve consist of two consecutive midpoints of the Chaikin's algorithm control points, and the Chaikin's algorithm control point between them.
Very impressive!
My solution uses the same recasting of Chaikin's algorithm in terms of the segment midpoints, but differs a bit at the end. Quadratic Bézier curves also go by the less fancy name of parabolas. Proving that each piece of the Chaikin curve is in fact the segment of a parabola follows immediately if we prove that a parabola has the following property:
For any two points A and B in a parabola, trace the tangents at these points, which meet at point P. Denote by M and N the midpoints of AP and BP, respectively. Then, the midpoint C of MN lies on the parabola.
There's probably an elegant solution of this using descriptive geometry, but I didn't bother to try it. If someone here wants to, please do and post it!
I did it the boring way using analytic geometry. It suffices to prove this for the parabola y = x^2, because any other parabola can be obtained by scalings and rotations of this one. Let A = (a,a^2) and B = (b, b^2). The equation of the tangent at A is y = a^2 + 2a(x-a), and at B is y = b^2 + 2b(x-b). We find P by setting
a^2 + 2a(x-a) = b^2 + 2b(x-b) => 2(a-b)x = a^2 - b^2 => x = (a+b)/2 => y = a^2 + a(-a+b) = ab => P = ((a+b)/2, ab)
Now, the point C is given by C = (A + 2P + B)/4 = (2a + 2b, a^2 + 2ab + b^2)/4 = (a/2+b/2, (a/2+b/2)^2). Notice that the y coordinate is indeed the square of the x coordinate, so the claim is true.
EDIT: Actually, now I see that this is not enough. We also need to prove that MN is tangent to the parabola. That's easy. The vector taking M to N is N - M = (B + P)/2 - (A+P)/2 = (B-A)/2 = (b-a,b^2-a^2)/2. Its slope is(b^2-a^2)/(b-a) = a+b, which is exactly the slope of the tangent at point C.
I was thinking about the five Platonic solids ...
... and whether it is possible to represent them in 3D space, using only integer coordinates for the vertices. The solid can be any size and rotated in any way, but all the vertices must have coordinates which are all integers.
The cube can be done just by taking combinations of 0 and 1 for the coordinates, like in the image below (taken from a Brown University course website):
But for the others, the problem doesn't seem so obvious.
1) Can you find a way to do it for the tetrahedron (solid in the top-left)?
2) Can you find a way to do it for the octahedron (solid in the center)?
3) What about the dodecahedron (bottom-left) and the icosahedron (bottom-right)?
Very interesting problem. From what I could see online, there are some algorithms to enumerate solutions for some cases. I would have to check if some can be simplified to provide a solution that always works.
Here's a partial result I could already obtain: this is impossible for the dodecahedron. Why? Because it's impossible to construct a regular pentagon using a 3d lattice. Proof follows.
Suppose you have three consecutive points of a regular pentagon A, B, C, all three with integer coordinates in 3d space. Then we evaluate the inner product (A-B)*(C-B). This should be equal to lA-B|^2*cos(108) because we must have |A-B|=|C-B| and the angle between two edges of a regular pentagon is necessarily 108 degrees. That implies cos(108)=(A-B)*(C-B)/|A-B|^2.
However, notice that the inner product (A-B)*(C-B) is an integer, because it's computed by products, suas and subtractions of integral numbers. Similarly, |A-B|^2 = (A-B)*(A-B) is also an integer, from similar arguments. That implies that cos(108) is a rational number, which is absurd, since cos(108)=(1-sqrt(5))/4 is in fact irrational. Since we reached a contradiction, our initial hypothesis that the pentagon exists must be false.
From what I could see online, there are some algorithms to enumerate solutions for some cases. I would have to check if some can be simplified to provide a solution that always works.
I'm interested in knowing what kind of algorithms you are referring to. I constructed my examples by finding an appropriate set of integer points, taking advantage of the fact that these solids are highly symmetric.
p4wn3r wrote:
Here's a partial result I could already obtain: this is impossible for the dodecahedron. Why? Because it's impossible to construct a regular pentagon using a 3d lattice.
Yes, actually the only regular n-gons that are embeddable in the cubic lattice are the 3-gon (equilateral triangle), 4-gon (square) and 6-gon (regular hexagon). The others (5-gon, 7-gon, 8-gon, and so on) are not possible because, similar to what you said, the cosine of the interior angle will be an irrational number.
Actually, I found out just recently that regular 5-gon, 7-gon, 8-gon, ... cannot be embedded in any lattice, regardless of the arrangement of points or the number of dimensions. This is because of an ingenious proof by descent that contradicts the existence of such a regular n-gon (if such n-gon can be embedded in the lattice, arbitrarily smaller ones can be generated from this in the lattice, contradicting the lattice property of a minimum distance between every pair of points). This proof only fails for the 3-gon (you get a larger triangle), 4-gon (you get the same square), and 6-gon (all generated points are the same making the hexagon degenerate).
Curiously, equilateral triangles (and regular hexagons) can be embedded in the integer lattice Zn for n>=3 dimesions, but not when n=2.
From what I could see online, there are some algorithms to enumerate solutions for some cases. I would have to check if some can be simplified to provide a solution that always works.
I'm interested in knowing what kind of algorithms you are referring to. I constructed my examples by finding an appropriate set of integer points, taking advantage of the fact that these solids are highly symmetric.
I was referring to this paper: https://arxiv.org/abs/0912.1062
The author's bibliography seems to have a lot of content regarding this problem.
Sorry for not answering early, it's been very busy since I moved to Munich. In any case, I'll drop the invitation here. If anyone wants to have a beer at Marienplatz, just PM!
Thanks!
It actually turns out the author made an entire paper titled "Platonic solids in Z3" which completely solves this problem, and more. (as if I could possibly be the only person on earth to come up with this problem...)
I never went as far as to try to characterize every single cube/tetrahedron/octahedron that was possible, but I'll just give the examples I had in mind:
1) Geometrically, a tetrahedron is "half" a cube, in the sense that it can be embedded inside a cube with its four corners touching four of the cube's corners:
(from math.stackexchange)
So if a unit cube has corners 000, 001, 010, 011, 100, 101, 110, 111, the tetrahedron has corners 000, 011, 101, 110. It can be checked that these four points are all equidistant from each other, with a distance of sqrt(2).
2) The integer points that are distance of 1 away from the origin (think of the sulfur hexafluoride molecule) form an octahedron:
(from math.brown.edu)
3) Finally the dodecahedron and icosahedron are not possible, because each one contains 5 points that form a regular pentagon, as shown by the red dots in the following image:
(edited from various wikipedia images)
And as p4wn3r mentioned already, a regular pentagon cannot be embedded in Z3. Thus, these two solids are not possible.
It took me a long time to write my post about Iterated Function Systems and Apollonian gaskets, but I think it was worth it because I got a very elegant solution to the problem.
Here is the medium post.
Here's a calculus problem:
A kite is to be constructed with side lengths 4,4,7,7 as shown below (not to scale):
We wish to maximize the area of the kite we construct. What is the value of x (the length of the dotted line in the diagram above) that gives the maximum area, and what is the maximum area?
We wish to maximize the area of the kite we construct. What is the value of x (the length of the dotted line in the diagram above) that gives the maximum area, and what is the maximum area?
I will be using the variables p and q as defined at MathWorld, so the desired area is A = 0.5 p q. In our case, p = sqrt(16 - 0.25 x2) + sqrt(49 - 0.25 x2) and q = x. To simplify some of the calculations, I'm using the additional variables e = sqrt(16 - 0.25 x2) and f = sqrt(49 - 0.25 x2).
The maximum value of the area occurs at a value of x at which the first derivative A'(x) = 0. Apply the product rule, chain rule, etc. to get A'(x) = 0.5 (e + f) [1 - x2/(4 e f)]. This means that either e + f = 0 or 1 - x2/(4 e f) = 0. There are no solutions to e + f = 0 among the real numbers. The other case can be rewritten as x2 = 4 e f. If you square both sides, expand the products in terms of x, and simplify, you get x = 56/sqrt(65) and A = 28.
There's a way to do it without calculus.
Let alpha be the angle between the sides of lengths 4 and 7. The area of the kite is 28*sin(alpha), so it's maximized for alpha = 90 degrees.
For this angle, one diagonal can be evaluated using pythagoras' theorem: sqrt(4*4+7*7) = sqrt(65).
Also, the quadrilateral is cyclic, so we can apply Ptolemy's theorem: x*sqrt(65)=4*7+7*4 => x=56/sqrt(65)
As a side note, I was introduced to that type of kite problem in a calculus course where it was expected to be solved in the same way as Dacicus did it (which I also did as well). After doing it that way, I found a simpler method very similar to how p4wn3r did it: Using trigonometry gives the angle between the sides of length 4 and 7 to be 90 degrees, and the rest of the problem easily follows from this.
(I also intentionally set up the problem to conceal this method. It's easier to see if you draw the vertical diagonal splitting the kite into two congruent triangles.)
p4wn3r wrote:
Also, the quadrilateral is cyclic, so we can apply Ptolemy's theorem: x*sqrt(65)=4*7+7*4 => x=56/sqrt(65)
Or just: The area of the kite is half the product of the diagonals: (1/2)*x*sqrt(65)=28 ------> x=56/sqrt(65).
(Yes, I know there are a dozen different ways to work out x.)
Just to clarify, I'm not saying that it's "bad" to use calculus to solve this problem. Any proof is as good as any other. However, one important part of studying math is to get used to different techniques, so you should always have the habit of, when you find a solution, see if it has some special properties, because often this highlights another way to tackle the problem.
In this case, if you solve with calculus you could try to guess what makes the quadrilateral that solves the problem so special, and then you would find that it's cyclic, has right angles, etc.
So, if you remember my previous posts studying the Apollonian gasket, I managed to improve to the point where I can do 4K zooms of it. See the video:
Link to video
Explanation here.
So I'm putting myself through Baby Rudin, and I was working exercises in the very first chapter.
Is it just me, or is problem 1.6 significantly more involved than problems 1-5? More involved than each individually sure, but also significantly more involved than all 5 of them combined. I just finished part (c), so I still have the final part to go, but I currently have 16 numbered statements (Defs, Lemmas, etc), and it spans 8 pages of latex so far. And I think I might be overthinking it.
For reference, Problem 1.6 is the problem where they ask you to define rational and then real exponentiation and prove some things about it.\
ETA: I guess since this is the math challenges thread, I might as well post the problem statement itself:
6. Fix b > 1.
(a) If m, n, p, q are integers, n > 0, q > 0, and r = m/n = p/q, prove that
(bm)1/n = (bp)1/q.
Hence it makes sense to define br = (bm)1/n.
(b) Prove that br + s = br bs if r and s are rational.
(c) If x is real, define B(x) to be the set of all numbers bt, where t is rational and t <= x. Prove that
br = sup B(r)
when r is rational. Hence it makes sense to define
bx = sup B(x)
for every real x.
(d) Prove that bx+y = bx by for all real x and y.
----
For this problem, you are armed only with the axioms of a field, the definition of an nth root. The fact that any set of reals with an upper bound have a least upper bound, and the Archimedean property.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Since this looks like a homework problem, I'll only give a hint.
Notice how Rudin proves that the n-th square root makes sense. He proves that x^(1/n) exists for x>0 in the way sketched below:
(a) He shows that the set A of real numbers y>0 such that y^n < x is bounded from above, and since the reals are complete, has a least upper bound.
(b) if we denote y = sup A, then there are only three options: y^n < x, y^n = x, y^n > x
(c) he then shows that if y^n < x, he can construct a larger y that still satisfies the inequality. similarly, if y^n > x, he can construct a smaller y still satisfying the inequality
(d) from this, assuming that y^n < x or y^n >x you conclude that y is not the least upper bound of A. Therefore, it must be true that y^n = x
From this, it makes sense to define x^(1/n) as the supremum of the set A = {y in R | 0 < y^n < x }. Notice that this is what we call an ineffective result. It merely shows by contradiction that a result exists, but provides no way to actually calculate it. This is pretty typical of the most fundamental results of real analysis.
Now, to your first exercise, you need to show that (b^m)^(1/n) = (b^p)^(1/q) if m/n = p/q. Notice that we have two root operations instead of one. Following Rudin's definition, we should look at these two sets:
A = { y in R | 0 < y^n < b^m }, B = { y in R | 0 < y^q < b^p }
Can you say something meaningful about these sets that could be useful to relate their supremum?
Since this looks like a homework problem, I'll only give a hint.
Not actually a homework problem. I've been out of school for a while. I'm just doing this independently for fun. I was just wondering, because I know people here *have* actually gotten math degrees, if 1.6 was somehow known for being involved. Here's what I've done so far.
1. Define exponentiation for negative numbers (and 0). This hasn't been done in the book yet, but is critical to justifying many things.
2. Show that addition and multiplication formulas of exponents holds for all integers. a^b a^c = a^(b+c) and (a^b)^c = a^bc
3. Show that for any base, b > 0 we can choose an n != 0, such that (b^n)^(1/n)
4. Show that roots combine in the manner we'd expect: (b^(1/m))^(1/n) = b^(1/mn)
5. Show that roots commute with powers: (b^m)^(1/n) = (b^(1/n))^m
6. Finally, we can complete part (a) and show that if m/n = p/q then (b^m)^(1/n) = (b^p)^(1/q), defining the rational exponents.
7. Complete part (b): b^r b^s = b^(r+s) for rational r and s
8. Show step 3, but for rational, rather than integer, powers and roots.
9. Show that if x and y are both larger than 1, then xy > x.
10. Show that if b>1 and n is positive, then b^n >= b.
11. Using 9 and 10, show that if x >= y > 1, then x^n >= y^n. (for positive integer n)
12. Prove for b>1, x>1, there's some positive integer n such that b < x^n.
13. Using 12, prove that given b>1, x > y there exists some rational number r such that x > b^r > y.
14. Using 11, Show that b^r is an upper bound of B(r)
15. Using 13, show that b^r is the least upper bound of B(r), defining the real exponents, completing part (c).
Then for part (d), I'll need to formalize and extend the argument alluded to in the appendix of chapter 1, where multiplication of reals is defined, but I haven't completed that quite yet (life is getting in the way), so I can't give you the steps, but I think I've got this covered. I'm sure I'll come up with *a* proof. Just wanted to know if 1.6 is notorious, or if I can expect the rest of the problem in Rudin to be like this, and 1-5 were the odd ones out, or if I'm begin entirely too careful, and this isn't expected, or if there's a fundamentally easier way that I'm missing.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Wait, the book does not even define exponentiation for integers or prove anything related to integer exponents, and yet you are expected to prove b^r b^s = b^(r+s) for rational r and s?
I was about to try answering, but considering how much the book does not allow to you assume, it's clear I know nothing about this subject, so I'm not going to bother.
As expected, the normal scheme is linear since you're working evenly. However, the new scheme is an interesting curve.
Is there any particular insight as to what this curve is, and why? (Let's assume the rate at which you do the workload is continuous as a function of time, rather than something to be updated every day.)
Edit: Changed the wording a bit.
The red circles are the control points. I have also displayed the midpoints (not necessarily accurately) between the control points as blue squares. n=0 is the starting configuration.
To go from n=0 to n=1, create new control points by taking the midpoint between the red circles and the blue squares. Delete the old control points (shown with hollow red circles). Finally, mark new midpoints between the new red circles. Notice: the previous blue squares will always remain as midpoints of the new configuration. So if we go from n=1 to n=2 similarly, all previous blue squares will be there as well, and new blue squares will be added.
This results in key point #1: the curve that the algorithm converges to is the completion ("limit") of all the blue squares generated by the algorithm.
Now a quadratic Bezier curve is just: For three points A, B, C, the quadratic Bezier curve on {A,B,C} is the parametric curve (1-t)2A+2(1-t)tB+t2C for t in [0,1]. Since translation of {A,B,C} just translates the corrsponding Bezier curve, let's assume A is the origin O, so the curve is just 2(1-t)tB+t2C. See the diagram below:
Here I've constructed B' (midpoint of OB), D' (midpoint of BC) and C' (midpoint of B'D'). By definition, C' is the point on the Bezier curve corresponding to t=0.5. Also notice that this construction parallels the construction in Chaikin's algorithm: If O and C are blue squares and B the red circle between them, we create new red circles B' and D', and a new blue square C'.
Key point #2: Each new blue square in Chaikin's algorithm can be generated by taking the point on the Bezier curve on each possible set of consecutive symbols {blue square, red circle, blue square} where t=0.5.
Finally, note that Chaikin's algorithm is recursive. So we just need to show that the Bezier curves are themselves "recursive"; that is, the Bezier curve on {O,B,C} can be split into two smaller Bezier curves, one on {O,B',C'} and one on {C',D',C}.
First, note that B' = B/2 and C' = B/2+C/4 . So the Bezier curve on {O,B',C'} is given by 2(1-s)sB'+s2C' = sB-s2B+s2B/2+s2C/4 = sB-s2B/2+s2C/4 . If we now take the Bezier curve on {O,B,C} and restrict it to t in [0,0.5] and let s=2t (so it goes from 0 to 1), we get 2(1-t)tB+t2C = 2tB-2t2B+t2C = sB-s2B/2+s2C/4 , the same as above.
So the Bezier curve on {O,B',C'} is just the Bezier curve on {O,B,C} restricted to [0,0.5]. By symmetry, the Bezier curve on {C,D',C'} is just the Bezier curve on {C,B,O} restricted to [0,0.5]; switching them around gives the Bezier curve on {C',D',C} is the same as the Bezier curve on {O,B,C} restricted to [0.5,1].
This gives key point #3: Bezier curves are "recursive" in the manner shown above; a starting Bezier curve can be recursively divided into smaller Bezier curves where the control points correspond to Chaikin's algorithm as above.
Thus, the key points all together say that, for a starting configuration, Chaikin's algorithm gives a composite Bezier curve composed of quadratic Bezier curves where the control points for each quadratic Bezier curve consist of two consecutive midpoints of the Chaikin's algorithm control points, and the Chaikin's algorithm control point between them.
... and whether it is possible to represent them in 3D space, using only integer coordinates for the vertices. The solid can be any size and rotated in any way, but all the vertices must have coordinates which are all integers.
The cube can be done just by taking combinations of 0 and 1 for the coordinates, like in the image below (taken from a Brown University course website):
But for the others, the problem doesn't seem so obvious.
1) Can you find a way to do it for the tetrahedron (solid in the top-left)?
2) Can you find a way to do it for the octahedron (solid in the center)?
3) What about the dodecahedron (bottom-left) and the icosahedron (bottom-right)?
(from math.stackexchange)
So if a unit cube has corners 000, 001, 010, 011, 100, 101, 110, 111, the tetrahedron has corners 000, 011, 101, 110. It can be checked that these four points are all equidistant from each other, with a distance of sqrt(2).
2) The integer points that are distance of 1 away from the origin (think of the sulfur hexafluoride molecule) form an octahedron:
(from math.brown.edu)
3) Finally the dodecahedron and icosahedron are not possible, because each one contains 5 points that form a regular pentagon, as shown by the red dots in the following image:
(edited from various wikipedia images)
And as p4wn3r mentioned already, a regular pentagon cannot be embedded in Z3. Thus, these two solids are not possible.
We wish to maximize the area of the kite we construct. What is the value of x (the length of the dotted line in the diagram above) that gives the maximum area, and what is the maximum area?
