The brilliant solution uses no lengths of sides or trigonometric functions, but it's very hard to see. (HINT: Draw auxiliary lines)
A colleague of mine, amazing at geometry, claims to have solved this problem in seven different ways (!). I only know two, the brilliant solution and a trigonometric one, which is easier to see, but requires a little manipulation of trigonometric functions.
I'll post the solution to the triangle problem here. If anyone wants a picture to understand it, feel free to ask.
Find the point F in AB so that the angle BCF = 20º. The triangle BCF is isosceles, since both base angles measure 80º, so BC=CF. Additionally, the triangle BCD is also isosceles, because CBD=BDC=50º, we conclude that CD=CF. Notice that triangle CDF is isosceles and has an angle of 60º (DCF). From this, we can see that CDF is not only isosceles, but equilateral. So, CD=DF=FC.
Now, consider triangle CEF. Finding its angles (40º, 40º and 100º), we can conclude it's isosceles and FC=FE. Finally, since DF=FE, we can see that triangle DEF is isosceles, so both base angles are equal. More specifically, FDE=FED= (180º - DFE)/2, meaning that FED=a+CEB= (180º - 40º)/2 , a + 40º = 70º, a=30º.
This is the most famous problem in V. Lidski's book "Problems in Elementary Mathematics" (if anyone would like to check it out, it has problems at an advanced level, if you have the skills to solve them, it'll greatly increase your mathematical knowledge, I recommend this book), possibly because at first, it seems easy to solve, but will soon drive people nuts while finding the solution. Today, almost everybody who studies math at olympic level knows this problem, it's used mostly to demonstrate the beauty and simplicity of synthetic solutions to geometry problems.
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
Nice solution, I completely understood it, though I doubt I would have found it by myself. Maybe my geometry skills are getting rusty :) It has indeed been quite some time since I faced these kind of geometry problems in a math course.
I didn't invent this (and I haven't solved it), but I saw it in another forum, so I thought it would fit perfectly here.
Maybe some of you remember the problem from basic vector math class, where a boat must travel across a flowing river to a certain point, and you need to calculate which direction the boat should point.
The captain of a certain boat is not so clever though, and just aims his boat straight at the destination, of course the boat starts to get pushed off course by the river current, but the captain keeps the boat pointed at the destination at all times. Eventually (assuming the boat can overcome the river current) the boat reaches the destination. What shape curve did the boat trace out?
Hmm, I can only get so far.
If the target is at the origin, and the boat is at position (x,y), then the speed of the boat will be the sum of the current flow and the boat's speed in still water. If the flow is f and flows in the y-direction (without loss of generality), then the x-speed of the boat is -bx/sqrt(x^2+y^2) and the y-speed is f - by/sqrt(x^2+y^2), where b is the boat's speed in still water.
This produces the differential equation
dy/dx = y/x - f*sqrt(x^2 + y^2)/bx
but, unfortunately, I cannot see how to solve it. Once solved, the boundary condition of the boat's initial position can be entered to find the path of the boat. This analysis does not assume that the boat starts on the x-axis -- that is, that the boat is trying to move straight across the river, perpendicular to the current. It might start from upstream or downstream of the target.
This produces the differential equation
dy/dx = y/x - f*sqrt(x^2 + y^2)/bx
but, unfortunately, I cannot see how to solve it.
Could it be that there is no closed-form expression that would describe the path, but that it can only be expressed iteratively (the same as with the n-body problem, where n > 2)? Is there any way of getting an approximation of the curve, even if by iterative means?
This produces the differential equation
dy/dx = y/x - f*sqrt(x^2 + y^2)/bx
but, unfortunately, I cannot see how to solve it.
Could it be that there is no closed-form expression that would describe the path, but that it can only be expressed iteratively (the same as with the n-body problem, where n > 2)? Is there any way of getting an approximation of the curve, even if by iterative means?
It's certainly possible (after all, the differential equation corresponding to the integral of the Gaussian distribution has no closed-form solution) but I'd be surprised if it actually were impossible to express. If I had time, I'd start with a series-based solution of the differential equation, and see what that produced.
This produces the differential equation
dy/dx = y/x - f*sqrt(x^2 + y^2)/bx
Hmm, this can be rewritten
dy/dx = y/x - (f/b)*sqrt(1+ (y/x)^2)
and then dy/dx depends only on y/x, not separately on y or x. (This is intuitively true, since the speed of the boat only depends on the angle towards the target, not the distance from it.)
Substituting y = vx,
dy/dx = v + x*dv/dx = v - (f/b)*sqrt(1 + v^2)
x*dv/dx = -(f/b)*sqrt(1+v^2)
\int(dv/sqrt(1+v^2)) = -(f/b)*\int(dx/x)
arctan(v)^2/2 = -(f/b) ln x + c
where \int is the integral symbol.
That's an implicit form for the curve. Making an explicit equation is left as an exercise.
That's actually a physics question regarding particle kinematics. Anyway, no problem asking here :)
This is easy if you use polar coordinates instead of cartesian.
Let's assume the destination point is at (0,0), the speed of the current is directed upwards in the y-axis direction and has magnitude w. The magnitude of the boat's speed is v at all times and its initial position is (a,0).
Now, what needs to be done is:
If you want to generalize more when the boat doesn't start at the x-axis, it's just a matter of inputting the right boundary conditions in the formula, but I think this is enough for just seeing the shape of the curve.
EDIT:
rhebus wrote:
dy/dx = v + x*dv/dx = v - (f/b)*sqrt(1 + v^2)
x*dv/dx = -(f/b)*sqrt(1+v^2)
\int(dv/sqrt(1+v^2)) = -(f/b)*\int(dx/x)
arctan(v)^2/2 = -(f/b) ln x + c
No, sir. /int(dv/sqrt(1+v^2)) = arcsinh(v) + c = ln (v + sqrt(1 + v^2)) + c
While we're on the subject of differential equations, here's a problem I came across...
Consider the following differential equation in 3 dimensions. D2 is the Laplacian operator, and x is the coordinate vector.
- D2f(x) + |x|2 f(x) = (2n + 3) f(x)
Those who know quantum mechanics will recognize this as a modified version of Schrodinger's equation for the isotropic quantum harmonic oscillator. And, in particular, that it only has square integrable solutions for nonnegative n.
However, f(x) = |x|-1 e-|x|2/2 is square integrable.
-Inf/Inf f(x)2 d3x = 0/Inf-1/10/2 pi |x|-2 e-|x|2 |x|2 dp d cos(t) d|x| = 4 pi 0/Inf e-x2 dx = 2 pi3/2
Now try plugging it into the equation and see what you get. Seems like a solution with n = -1, doesn't it? It's not. Why not?
I decided to actually find y(x) explicitly in the above problem. I'm not going through the derivation, but suffice to say you can do it without transforming to polar coordinates.
If the boat starts at (a, z*a) and the velocity ratio is R = w/v, then we have...
y(x) = x * (z * cosh(R * ln(a/x)) + sqrt(1 + z2) * sinh(R * ln(a/x)))
If R <1> 0. The trajectory will arrive at the origin.
If R > 1, then the sinh and cosh terms dominate, and the trajectory diverges from the origin.
If R = 1, then the two influences cancel each other out. The trajectory arrives at the y-axis, but not at the origin.
There are 29 distinct pentacubes (combinations of five cubes in three dimensions, similar to tetrominoes). Is it possible to construct a 5x5x5 cube from pentacubes without using a particular pentacube more than once? Obviously four pentacubes would be unused as there is only room for 125 blocks.
I don't actually know the answer to this, but if you do I'd love to see your solution.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
well, if you want proof, first attempt would be a brute force algorithm:
function recurse()
{
E = first place that's empty (needs a consistent order of the 5x5x5 cube's places)
report success if no empty place found
for all pentacubes P not yet used:
for all (3 to 24) unique orientations O of the pentacube P:
for all 5 cubes C of the pentacube P:
rotate P into orientation O, locate it so that C fits into E
if P fits into the 5x5x5 cube:
insert P
recurse()
remove P
}
The complete search tree suggests a running time past the heat death of our universe. Even though a lot of subtrees will be cut short, I don't think this'll lead to the solution unless it's lucky enough to find a working combination quickly.
In other words, we need to be smart about it, but so far I haven't had any idea for a either a smarter construction or a structural proof of impossibility.
I guess the best approach is to construct the cubes and spend a few hours fiddling with them, that may just find a solution.. but I don't feel like spending that effort ;)
Yes, brute force is rather out of the question. That's one of the reasons why it'd make a good physical puzzle -- I'm considering trying to make one out of wooden cubes but I'd like to know that there is a solution (and, ideally, what the solution is) before I start work.
EDIT: I've managed to create a 5x5x5 cube in Blender that re-uses one pentacube once (the one that's a 2x2 square with an extra piece tacked on in the same plane). A render of the cube (minus the duplicated piece) and the unused pentacubes:
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
With about 24,000 (29 choose 25) different choices of pentacubes to work with and millions of ways to stack them, I'm almost sure it can be done.
I'm a little ashamed to say you've gotten me working on this all day. I've been looking for 5x5 tilings of the 12 extruded pentominos. After I'm done, I'll use the remaining pieces to fill in the 3x5x5 block. It's slow, but not especially difficult.
I just now found a solution. It was a big help to start out by placing as many of the 3D pieces as possible, saving the comparitively easier-to-work-with 2D pieces for the endgame. I've put my solution online as an image sequence here and as an animation here. In each case the four pieces shown at the end are the pentacubes that weren't used. It's entirely possible that there are solutions that use those pieces, though.
Solving this was fun. And now I can use this as the basis for making a real-world version of the puzzle.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
That was a really cool problem Derakon, I wish I had a chance to try it before it was sovled! What program did you use to help you visualize and experiment to try to find the solution?
There are almost certainly lots more solutions, so feel free to try to come up with your own! I apologize for rushing my own solution out, but I do have an ulterior motive...
I used Blender to find the solution. It's not really designed for this kind of thing (for example, it cares not a whit if two blocks occupy the same physical space), but it worked well enough.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
While we're on the subject of differential equations, here's a problem I came across...
Consider the following differential equation in 3 dimensions. D2 is the Laplacian operator, and x is the coordinate vector.
- D2f(x) + |x|2 f(x) = (2n + 3) f(x)
Those who know quantum mechanics will recognize this as a modified version of Schrodinger's equation for the isotropic quantum harmonic oscillator. And, in particular, that it only has square integrable solutions for nonnegative n.
However, f(x) = |x|-1 e-|x|2/2 is square integrable.
-Inf/Inf f(x)2 d3x = 0/Inf-1/10/2 pi |x|-2 e-|x|2 |x|2 dp d cos(t) d|x| = 4 pi 0/Inf e-x2 dx = 2 pi3/2
Now try plugging it into the equation and see what you get. Seems like a solution with n = -1, doesn't it? It's not. Why not?
I am not particularly well versed in the mathematics involved in packings and tilings and the like, but my understanding is that it is helpful (for humans) to consider a finished 5x5x5 cube as being "tiled" like a checkerboard. (Color each 1x1x1 cubie a solid color.) That leads to a number of obvious parity arguments, for example, a valid solution cant put pentacubes in a configuration that has two adjacent cubies of the same color.
If you're looking for a fancy computer algorithm, unsurprisingly there is a way to convert tiling problems into a matrix that you can calculate an exact cover of. For example, if there are 29 distinct pentacubes, and you want to tile a 5x5x5 cube (125 cells big), the rows of your matrix will be 29+125 columns long.
Otherwise filled with 0s, each row will contain a single 1 within the first 29 columns identifying the pentacube being used, and five 1s within the next 125 columns indicating which of the 5x5x5's individual cells are occupied by the pentacube in question. Construct a comprehensive listing of all such rows for each pentacube. (For example if there are 100 different ways to place pentacube-1 in a 5x5x5 cube, pentacube-1 would have 100 rows in this matrix. I made the number 100 up.)
Put all 10,000 (or whatever, made this number up) rows together into one big 10,000 by 154 matrix, and then calculate an exact cover. (That is, is there a subset of rows containing exactly one 1 in each column?) I won't go over a good algorithm for this, since I don't know one off the top of my head. I know that efficient algorithms exist and have been written about extensively by the likes of Conway, Knuth, etc.
(a) Let x1 and x2 be the roots of the polynomial P(x) = x^2 - S x + P , S and P real numbers.
Find a polynomial Q(y) of degree 3, with coefficients in terms of S and P, where is a root of Q(y)
(b) Consider the polynomial F(x) = x^3 + a x^2 + b x + c with real coefficients. Find the value of t, so that the coefficient of y^2 in F(y + t) is 0.
(c) Find all roots of the equation x^3 - 3 x^2 + 2 x - 1 = 0
Nobody was interested in the above question.
It was actually the simplest proof I know for Cardano's formula that I tried putting into a question.
(a) Elevating both sides of the equation to the cube we get: y3 = x1 + x2 + 3(x1x2)1/3(x11/3+x21/3), which can also be written as: y3 = S + 3 P1/3 y . Therefore, the polynomial Q(y) = y3 - 3 P1/3 y - S is the answer.
(b) Substituting x = y + t:
F(y+t) = y3 + (a+3t)y2 + (b+2at+3t2)y + (c+bt+at2+t3)
It's easy to see that t= -a/3 eliminates y2's coefficient.
(c) As you can see, this cubic doesn't admit rational roots, so we have to solve it by Cardano's method. It gets really big, I won't do it because I'm lazy leave it as an exercise for the reader. The process is: using (a), you can express a root of the equation in terms of the roots of a quadratic function if its coefficient for the quadratic term is zero. The equation doesn't satisfy this, but we can get rid of the coefficient using (b). After the first root is found, we can use Briot-Ruffini's algorithm to reduce it to a quadratic equation.
Additionally, (c) should also discourage you from using this method, since many times it doesn't produce useful results. For example, if one were to calculate cos 20º with cos 60º = 4 cos320º - 3 cos 20º or 4x3 - 3x - 1/2 = 0 , he would get:
cos 20º = (1/16 + i * sqrt(3)/16)1/3 + (1/16 - i * sqrt(3)/16)1/3
That doesn't tell much about cos 20º, because it has complex numbers. It can actually be demonstrated that any finite expression with radicals for cos 20º must involve complex numbers with non-zero imaginary part.
f(x,y) = (xy+1)^2 + x^2
As a sum of two squares, this is clearly nonnegative everywhere, and zero if and only if x=0 and xy=-1 (and thus can't be zero anywhere). For arbitrarily small x, we can find a y satisfying xy+1=0, and thus f gets arbitrarily close to zero.
I actually got this from considering x as a quadratic with y fixed, and making c - b^2/4a arbitrarily small as y varies. I eventually came up with (y^2+1)x^2 + 2xy + 1, which turned out to simplify to the form above.
If you want to generalize more when the boat doesn't start at the x-axis, it's just a matter of inputting the right boundary conditions in the formula, but I think this is enough for just seeing the shape of the curve.
EDIT:
is a root of Q(y)
(b) Consider the polynomial F(x) = x^3 + a x^2 + b x + c with real coefficients. Find the value of t, so that the coefficient of y^2 in F(y + t) is 0.
(c) Find all roots of the equation x^3 - 3 x^2 + 2 x - 1 = 0
