EventHorizon

You are a scientist whose had a bad day and wish to take it out on your favorite maze running rodent. The setup: 1. The maze is set on a nxn grid, where n is some large integer. 2. The mouse will always move in the direction that will get it to the cheese the quickest, but can only move north, south, east, and west. The mouse prefers different cardinal directions consistently (it only matters that it is consistent, you can choose the ordering to maximize time), but only uses this preference to break ties when two paths of equal lengths are encountered. Assume the mouse takes 1 second to move from one square to another. 3. At any time, you can pause time and place a wall (essentially a brick the size of the square) in a grid square. Once time starts again, the mouse instantly determines the new optimal path and follows it. Obviously, if the mouse is even partially in the square you cannot place a wall there (your day wasn't _that_ bad). 4. Walls cannot be removed once placed. 5. You can place the cheese and start the mouse anywhere in the maze, but you cannot move the mouse or cheese once initially placed. 6. You must always leave at least one path open to the cheese from the mouse's current location. The goal: Make the mouse take as long as possible before it gets the cheese. Scoring criteria: Score = time taken/(n*n). This essentially measures how many times on average each square (even blocked off ones) is traveled through by the mouse. What is the best strategy you can come up with (and the score associated with it)?

You can answer this one using a method quite similar to that of my answer for "circular dice." In fact, it is similar to prime's simple answer.

ugg....I left off a set of parenthesis... the equation should be y=(z^(z^x)-x)/(p(z)-x)

What I meant is it will converge if started infinitesimally close to the equilibrium and the slope at the equilibrium is in the range (-1,1). The remaining math work is to show that it can get arbitrarily close to p(x) for x in the range (1/(e^e),e^(1/e)]...no matter where it is started.

Why is the derivative a deciding factor for the convergence of those oscillating values? Consider the following... Let the slope at p(x) be -1+e = -(1-e). Let a1 = p(x)-d. When very close to the intersection/equilibrium, they are basically straight lines crossing. a2 = p(x) + (-d*-(1-e)) = d(1-e). What I'm doing here is simply treating them as straight lines and seeing what the next value will be. a3 = p(x) + d(1-e)*-(1-e) = p(x)-d(1-e)^2 ... an = p(x) + ((-1)^n) * d * (1-e)^(n-1) if e is greater than 0, (1-e) is less than 1 and the error is decreasing. If e is 0, there will be no movement. If e is negative (e.g., the slope is less than -1), then (1-e) is greater than 1 and the error is increasing. What this is saying is that the series will converge if the slope at the equilibrium is in the range (-1,1). Not only that, but the closer the slope is to 0, the faster the convergence (alluded to in a previous post). Therefore, if the derivative at the equilibrium is less than -1, the series will not converge to p(x). When x = 1/(e^e), the slope at the equilibrium is exactly -1. With a little more math work (described in my last post) we may be able to show that it will converge for all x in (1/(e^e),e^(1/e)]. Consequently.....the slopes at the equilibrium for x values of 1/(e^e) and e^(1/e) are -1 and 1 respectively.

I thought I would look at the following equation (again using z and p(z) as opposed to x's to leave x for graphing), y=(z^(z^x)-x)/p(z)-x, (obviously undefined at p(z)) This equation represents the percent change in the error (distance to equilibrium) after two more exponents. If this equation has a minimum greater than 0, then the remaining distance will be at most 1-min(y) (=less than 1) times the previous distance after two more exponents. The error after 4 more exponents will be (1-min(y))^2 times the previous error, etc. Obviously, we can get the error as small as desired because the multiplier is less than 1. I've checked the minimum of the equation using a calculator (yeah, I'm lazy.....and the math was getting a little ugly) for a number of z values between 1/(e^e) and .0659928, and it seems to me that the only time it reaches 0 is at 1/(e^e). So it seems you may be right in thinking it was some sort of precision error/drift. I may try the math again later to try and get a more rigorous proof....

Proof of (1) is fairly simple. Set the first derivative to zero. As for (2), it seems you would need the graph to approach and only touch the line y=x once but not cross it. The only one that does this is x=e^(1/e), which was shown to converge to e (from below). So...no other convergence points. (I thought I would add in a little more explanation now that I reread (2). The slope of the graph of r^x at the point of convergence determines how quickly it will converge. Which is why it would need to not cross if the series was to slow too much to converge.)

Thanks. I was a little unsure that 1/(e^e) would converge....if the slope at the intersection is really -1, then there isn't much pushing the series towards the intersection point when very close to it. But barely beyond it, it seems like it should converge. I'll think about it more and perform similar calculations and post any interesting results I stumble on.

Possibly. I've tried for a little while to find a way to calculate it exactly and looked around on the net, but can't find it as of yet. I may try again a little later. It seems that X^(1/X) is just a hard function to work with.

I just found out the smallest x such that a stable p(x) exists! Instead of x, I'll use z (and p(z)) to leave x as an independent parameter for graphs etc. The reason z^z^z^z^z.....diverges with small values of z is that the slope of y=z^x is less than -1 when it intersects the line y=x. This means that the intersection is an unstable equilibrium because z^x will be further from the equilibrium than x. To find the specific value of z such that the slope at the point of intersection is -1, I did the following. First I took the derivative of y=z^x with respect to x. dy/dx = (ln z)(z^x)dx Since the intersection is where y=x, this leaves me with a system of 2 equations and 2 unknowns. Let w = p(z). -1=(ln z)z^w w=z^w -1=(ln z)w -1/w = ln z e^(-1/w) = z (e^(-1/w))^w=z^w e^-1=w w = 1/e -1/(1/e) = ln z -e = ln z e^-e = z So the lower bound for x (from OP) that converges is e^-e ~ .066 So the range for x for which the series can converge is [1/(e^e),e^(1/e)], and their corresponding p(x) values are 1/e and e respectively.....seems fitting, don't you think? So, for the record, here are the ranges for x and what equilibria they produce... Range, Equilibria (-inf,0), no idea... 0, diverges by alternating 1's and 0's (0,1/(e^e)), one unstable equilibrium in the range (x,1/e), but ends up alternating between two values (which themselves converge) if not started on the equilibrium [1/(e^e),1], one stable equilibrium in the range [1/e,1] (1,e^(1/e)), one stable equilibrium (somewhere in the range (x,e)) and one unstable equilibrium (greater than e) e^(1/e), an equilibrium at p(x)=e that is stable from below and unstable from above ((e^(1/e)),inf), no equilibria (diverges)

Since my first post has mostly been ignored, I thought it would be good to explain it better. It answers questions such as why the "paired points" exist, which x's converge, why x>e^(1/e) does not converge, etc. If you look at the graph of y=sqrt(2)^x and compare it to the graph of y=x, you'll notice that sqrt(2)^x > x over the ranges (-inf,2) and (4,inf). sqrt(2)^x < x over the range (2,4). This shows you that 2 is a stable equilibrium of the series (if you start somewhere in the range (-inf,4), you will end up at 2), and 4 is an unstable equilibrium (if you start near but not directly on it, you move away from it). Here I used x and y as the independent and dependent variables for a graph (as opposed to the variable in the OP). The graph is used here to show that given ai = x, ai+1 = y. It essentially shows how the numbers move in the series given any and all starting points. If x = sqrt(2)^x, then x is an equilibrium point. This works for x=2,4. But then I show what the graph looks like around those ranges, and you can see that the series converges to 2 if initially started less than 4, to 4 if started at 4, and diverges to infinity when starting greater than 4. I then discussed ranges for the x given in the OP. if x is in the range (0,1), there is one stable equilibrium at y satisfying x = y^(1/y), where x < y < 1. These series actually alternates between above p(x) and below it. It looks like I didn't try a small enough x initially because it looks like somewhere between .05 and .1 it starts to tend to stabilize on alternating between two values. So in the range [.1,1) it converges as I said before, but in the range (0,.1) I haven't quite figured out the exact value at which it stabilizes on two alternating values. This should have been apparent due to x=0. 0^1=0 => 0^0 => 1 (according to google)....so it will alternate between 0 and 1. if x is 1, there is one stable equilibrium at 1. Obviously if you have 1^z = 1, 1^1=1. So for any starting point, it converges on 1 quickly. if x is in the range (1,e^(1/e)), there is one stable equilibrium (somewhere in the range (x,e)) and one unstable equilibrium (greater than e) both satisfying x = y^(1/y). These follow the same pattern as my first example with x=sqrt(2). The graph between the two points is less than the graph of y=x, which makes the lesser of the two points stable and the upper unstable. if x = e^(1/e), there is one unstable equilibrium at e. I was incorrect saying that it was a stable equilibrium here. It is stable from below, but diverges from above. You can see this because (e^(1/e))^z > z for all z except z=e where it is equal. It asymptotically approaches e from the bottom, but if you start just above e it starts out moving slowly away and then only increases the speed at which it diverges. if x is in the range (e^(1/e),inf), there is no equilibrium.... the graph compared to the graph of y=x shows that the number always increases. A simple proof of this is the following (let the x from the original post be z to allow x to be the independent variable in the graph). Look at the graph of y = z^x compared to y=x where z is in the range (e^(1/e),inf). The graphs do not touch or cross. You can determine the minimum of the function y=(z^x)-x, which will be a positive number (call it alpha) which represents the smallest change in the series. This shows that as the series continues, the next element in the series will be at least alpha greater than the previous value. Since the series will always be increasing by at least a given positive number, it cannot converge. The series essentially start with x (from the OP) (or equivalently the power/multiplicative identity, 1), which shows that you cannot get to p(x) equilibria values greater than e without starting directly on them.

Oops....it looks like it is stable from below, but unstable from above....a saddle point?

If you look at the graph of y=sqrt(2)^x and compare it to the graph of y=x, you'll notice that sqrt(2)^x > x over the ranges (-inf,2) and (4,inf). sqrt(2)^x < x over the range (2,4). This shows you that 2 is a stable equilibrium of the series (if you start somewhere in the range (-inf,4), you will end up at 2), and 4 is an unstable equilibrium (if you start near but not directly on it, you move away from it). As for the range of values that converge (where x is the x stated in the OP).... if x is in the range (0,1), there is one stable equilibrium at y satisfying x = y^(1/y), where x < y < 1. if x is 1, there is one stable equilibrium at 1. if x is in the range (1,e^(1/e)), there is one stable equilibrium (somewhere in the range (x,e)) and one unstable equilibrium (greater than e) both satisfying x = y^(1/y). if x = e^(1/e), there is one unstable equilibrium at e. if x is in the range (e^(1/e),inf), there is no equilibrium.... the graph compared to the graph of y=x shows that the number always increases. if x is negative, complex numbers make things difficult.....

Repeat! http://brainden.com/forum/index.php?showtopic=1502 Might want to look at my answers in that thread....they don't need extra 0's or the three's required for cube roots.

yeah......Of course you can increase the degree of the polynomial and throw it all in a matrix to get coefficients that will work....but do you really think the author meant for all these to be high degree polynomials? And theshredder157...you missed #1 (your 2 is equivalent to mine). But great job getting number 4 (I'm not positive that's correct since I didn't write the problem....but it's nice and concise) I just noticed that you (theshredder157)are the op. You apparently have some errors in the lists you provided if those are the right formulas.

Since noone is guessing, Here's the answer... Now that was fun....wasn't it?

Given the first hat problem is very related....I got this in no time flat.

What are the next three numbers in this sequence? And how was the sequence created? What positive integers are skipped, and how long is the sequence? 3, 1, 6, 2, 9, 14, 5, 12, 11, 8, 15, 19, 21, 18, 23, ?, ?, ?

Yup, that's what time it was. Good job.

(1) This one is taken from a math puzzle website (which I cannot name here due to mods removing offsite puzzle references). What are all possible pairs of integer values that satisfy the following equation? And can you prove there are no more? x^y = y^x (2) I couldn't sleep one night, and noticed the clock's time had an interesting property. Let the clock's time be x:yz am. x is a factor of yz (not y*z, but simply putting their digits together), z is a factor of xy, and y is a factor of xz. Not only this, but yz/x = xy/z. Additionally, x, y, and z are all unique. What are x, y, and z? I'm not sure if there is more than one solution to this one....and if there is I can add another constraint.