Easy math puzzles

Quote: Wizard

p.s. Why am I advised to capitalize Googleplex?
link to original post

I think "googolplex" is the number, and "Googleplex" is Alphabet City.

I think that the answer depends on how the location of the portal is chosen. I assume that either path is equally likely but the probability distribution of the distance along the correct path is important (and without a rigorous definition of this we can't calculate the expected distance traveled, so we can't minimize it).

The probability distribution can't be uniform because there can't be a uniform probability distribution over an unbounded set (you can have one over an infinite set, like all the real numbers between 0 and 1, but it needs to be bounded -- there's no uniform probability distribution over all the positive reals)

Quote: Wizard

An Evil Wizard transports you to a distant planet, where you are placed at the beginning of two different paths. As in the Led Zeppelin song, there are two paths you may go down and there's always time to go back and switch to the other path any time you wish as many times as you wish.

Somewhere, on one of the paths, is a portal taking you back home.

The path with the portal has a finite but unknown distance (for example, an inch or a Googleplex light years). The other is infinitely long.

What strategy should you take to minimize the expected walking time to find the portal?

p.s. Why am I advised to capitalize Googleplex?
link to original post

This problem has already been posted twice before and never answered. Even the “googleplex” term was used. Formerly it was framed as an evil wizard in an infinite “but not completely infinite” desert. Don’t waste your time on it

Quote: Ace2

This problem has already been posted twice before and never answered. Even the “googleplex” term was used. Formerly it was framed as an evil wizard in an infinite “but not completely infinite” desert. Don’t waste your time on it

I'm fairly sure that the point I made above is the reason it hasn't been answered (the question is not well defined) but I'd like to get your feedback (particularly if I'm wrong)

Quote: Wizard

Quote: ThatDonGuy

My "gut" answer

Label the two paths A and B, and let A(x) and B(x) be the points on each path that are distance x from the starting point.

Start by walking on path A, then the turnaround points are A(1), B(2), A(3), B(4), A(5), B(6), and so on.
The exact distance from, say, 0 to A(1) is irrelevant.

link to original post

You are right about establishing turnaround points. I would say the distances between them are very relevant. That is the point of the problem. For example, if you walked 100 miles down path A and turned around and eventually returned to path A, after not finding the portal on path B, then you wouldn't turn around again at 101 miles from the junction.
link to original post

If every mile of each path is essentially equally probable to contain the portal then after taking a hundred years to walk 1,000,000 miles down an infinite path why would you turn around and spend the next 100 years walking back to your point of origin? It would have profited you more to spend that next 100 year increment walking another 1,000,000 miles down the first path because you would have a chance to find the portal during that time.

Solution to the Evil Wizard/Two Paths Puzzle
You have been walking down the infinite path for some unremembered number of years when you find the Cemetery of Forgotten Books, an infinite labyrinth of rooms with shelves that contain every book ever written by humanity -whether or not it was ever published. You start browsing through the library and encounter a young woman - a young Sydney Sweeney. For this is an infinitely long path that you may walk for an infinite amount of time, and surely one can encounter anything on such a path?

And young Sydney Sweeney walks toward you, smiling -beaming with happiness - saying "It has been so long since I have seen another human being." Her eyes look down in momentary shyness and she continues "And I have always been attracted towards older men, particularly nerdy men of great intelligence." She then walks into the oval of your arms and presses her body against yours. She says "I've been so lonely. Please stop your endless search for the 'Portal to Home' long enough to spend a night or two with me."

She tilts her head up. She is young, beautiful. She holds the world in her eyes.

The two of you kiss, at first hesitantly then passionately. Nature takes its course.

You awake the next morning and Sydney is standing there with a tray in her hands, serving you breakfast in bed. Bread, exotic cheeses, fresh fruit, eggs, bacon. And the smell of fresh apple pie coming from the next room. Sydney smiles, "Yes. I also enjoy baking."

Ten years have passed. You sit in a seat close to the fire, with Sydney by your side, reading an unpublished work by JRR Tolkien. Near you, waiting to be read, are unpublished works by Dostoyevski and Lee Child. But suddenly, a road-weary Mike Shackleford walks into the room and looks at you quizzically. "Why are you just sitting there?" he asks. "You should be looking for the Portal to Home."

"But I am home." you reply.

"My puzzle statement says that you are looking for a Portal to Home."

You say. "The puzzle statement also says that we live forever and have been given the gift of an infinitely long path to walk. It is folly to look for a portal. I believe we should keep walking until we find our heart's desire and then stop for as long as we want."

Michael says "But that's not the statement of the puzzle."

Sydney speaks up. " Well, I have a lonely sister who lives here who would be perfect for you. She is better looking than me, intelligent, a great conversationalist, she has a great wine cellar and a two word tattoo on the small of her back, right above her butt cheeks.

"A two word tattoo? I do love word puzzles, so very much. Tell me, what does her tattoo say?"

And Sydney replies :

Michael says " Uh...ahem. Very tempting. But I am a mathematician and I need to be true to my puzzle."

Sydney counters with "Well, our Cemetery of Forgotten Books has lost letters about mathematics by Euler, translated into English. There's an unpublished book with a simple proof of the Riemann Hypothesis. Lost books on combinatorial theory."

Shaken, Michael says: "But there's a portal to home somewhere on these two paths. And you know I like to hike."

"Yep" she says "and just a short hike down the road there's a Cemetery of Forgotten License Plates. Infinite labyrinth thingy, goes on forever."

The room grows silent and the silence stretches for minutes.

At that moment Sydney's sister walks into the room, and she can indeed make blind men see. She turns to the Wizard and says " Sir, will you be my hero?"

And the Wizard, ever the gentleman, says

So you see, dear reader, some puzzle statements are so fantastic that men can find wisdom in their solutions in unexpected ways.

Quote: Wizard

Quote: ThatDonGuy

My "gut" answer

Label the two paths A and B, and let A(x) and B(x) be the points on each path that are distance x from the starting point.

Start by walking on path A, then the turnaround points are A(1), B(2), A(3), B(4), A(5), B(6), and so on.
The exact distance from, say, 0 to A(1) is irrelevant.

link to original post

You are right about establishing turnaround points. I would say the distances between them are very relevant. That is the point of the problem. For example, if you walked 100 miles down path A and turned around and eventually returned to path A, after not finding the portal on path B, then you wouldn't turn around again at 101 miles from the junction.
link to original post

It seems a unit vector is needed, if this is going to be a problem that includes proximation and quantization of distances. For example, you mentioned coming out of a subway and looking for your hotel knowing it was on that street but could be in either direction. The first thing I would do is look in both directions hoping I could see it, using sight as an alternative to motion. How far you can see, thus how close you have to be to the portal to have "found it" seem like they should have some effect on the turnaround points.

Quote: SkinnyTony

I think that the answer depends on how the location of the portal is chosen. I assume that either path is equally likely but the probability distribution of the distance along the correct path is important (and without a rigorous definition of this we can't calculate the expected distance traveled, so we can't minimize it).

The probability distribution can't be uniform because there can't be a uniform probability distribution over an unbounded set (you can have one over an infinite set, like all the real numbers between 0 and 1, but it needs to be bounded -- there's no uniform probability distribution over all the positive reals)
link to original post

Oy. Okay, let's say the path with the portal has distance x and the other path is infinitely long. The portal is chosen random according to the uniform distribution between 0 and x. In simple terms, all locations are equally likely.

Quote: Ace2

This problem has already been posted twice before and never answered. Even the “googleplex” term was used. Formerly it was framed as an evil wizard in an infinite “but not completely infinite” desert. Don’t waste your time on it
link to original post

No comment.

Quote: charliepatrick

still stumped but ideas

It sounds like an interesting problem however I'm quite busy this weekend. So these are my initial thoughts.

I had assumed for simplicitiy that there was an East-West path and with one road going West and the other road going East. There were mile markers and for simplicity the prize is at one of those markers. I had assumed that initially the prize had equal probability of being East or West of the starting position (MM0).

It became apparent that the probabilities of where the prize is couldn't be uniform but must be something like the setter picks a path at random and then works their way along the path. At each Mile Marker they roll a multi-sided die and (say) if it's a 1 drops the prize otherwise moves on. This means that at MM0 the probability distribution along a path is similar to being at MM1.

As has been said you travel to a mile point and have to ascertain whether it's best to look at the next one or turn round. The upside is finding the prize at the next MM quicker, and the downside is if the prize is at all the other MMs, then you've lost 2 miles.

For instance if the setter tossed a coin, at the beginning the chance of [the prize] being at MM1E is 1/4 (MM2E=1/8 etc.). At the beginning the chances of being West is 1/2 and of being East beyond MM2E=1/8. So at MM1E the chances are now W=4/6, MM2E=1/6, MM2+E=1/6. The additional distance saved for MM2E is at least 4, and probably 6. But there is a 5/6 chance you add 2 miles to the journey. So for it's best to tun round at MM1E.

I was then going to look at different probabilities and spot a pattern, but it does look as if you turn round when the above calculation says the chances of (the downside) being West [x 2 miles] outwieghs the chances of (the upside) being further East (x >4 distance from staring position). Given you know the shape of the probaibility curve, you can now look at the differential as you change the distances involved.

This would then give an answer such you turn round when the chances of being further East is lower than p.

The problem I see is you don't yet know the turning point for the West leg, so can't tell the "upside" accurately. It seems obvious you go further along the West leg than when you first turned on the East leg. However you do know the chances of being East or West are identical when you get to the same distance.

link to original post

You may assume you know the exact distance from the junction, or starting point, at all times. As I just wrote in other post, the portal is placed randomly and according to a uniform distribution between 0 and the end of the path with the portal. Again, the other path is infinitely long.

Quote: AutomaticMonkey

It seems a unit vector is needed, if this is going to be a problem that includes proximation and quantization of distances. For example, you mentioned coming out of a subway and looking for your hotel knowing it was on that street but could be in either direction. The first thing I would do is look in both directions hoping I could see it, using sight as an alternative to motion. How far you can see, thus how close you have to be to the portal to have "found it" seem like they should have some effect on the turnaround points.
link to original post

Let's assume for the sake of the problem you are blind and don't know you're at your hotel until you actually get there (because the doorman knows you and greets you).

As a hint, this problem requires only simple differential calculus to solve.

Quote: gordonm888

You have been walking down the infinite path for some unremembered number of years when you find the Cemetery of Forgotten Books, an infinite labyrinth of rooms with shelves that contain every book ever written by humanity -whether or not it was ever published....
link to original post

That was good, thank you. May I have your permission to publish this in a book I may write on logic puzzles?

Quote: Wizard

Quote: gordonm888

You have been walking down the infinite path for some unremembered number of years when you find the Cemetery of Forgotten Books, an infinite labyrinth of rooms with shelves that contain every book ever written by humanity -whether or not it was ever published....
link to original post

That was good, thank you. May I have your permission to publish this in a book I may write on logic puzzles?
link to original post

Yes. Glad you enjoyed it. I started writing it and it went in unexpected directions.

Quote: Wizard

Quote: SkinnyTony

I think that the answer depends on how the location of the portal is chosen. I assume that either path is equally likely but the probability distribution of the distance along the correct path is important (and without a rigorous definition of this we can't calculate the expected distance traveled, so we can't minimize it).

The probability distribution can't be uniform because there can't be a uniform probability distribution over an unbounded set (you can have one over an infinite set, like all the real numbers between 0 and 1, but it needs to be bounded -- there's no uniform probability distribution over all the positive reals)
link to original post

Oy. Okay, let's say the path with the portal has distance x and the other path is infinitely long. The portal is chosen random according to the uniform distribution between 0 and x. In simple terms, all locations are equally likely.
link to original post

The answer is going to depend on the value of x. More specifically, the optimal "turnaround points" are going to be a function of x.

We can get a worst case of 3x and an average of x by following one path for a distance of x, then turning around and switching paths. This seems to go against the spirit of the question.

If we don't know the value of x then we are back to the issue of having a problem that's not well defined. This kind of reminds me of the St Petersburg paradox (the "paradox" comes from the fact that the probability distribution that's described in the question doesn't exist)

Quote: SkinnyTony

Quote: Wizard

Quote: SkinnyTony

I think that the answer depends on how the location of the portal is chosen. I assume that either path is equally likely but the probability distribution of the distance along the correct path is important (and without a rigorous definition of this we can't calculate the expected distance traveled, so we can't minimize it).

The probability distribution can't be uniform because there can't be a uniform probability distribution over an unbounded set (you can have one over an infinite set, like all the real numbers between 0 and 1, but it needs to be bounded -- there's no uniform probability distribution over all the positive reals)
link to original post

Oy. Okay, let's say the path with the portal has distance x and the other path is infinitely long. The portal is chosen random according to the uniform distribution between 0 and x. In simple terms, all locations are equally likely.
link to original post

The answer is going to depend on the value of x. More specifically, the optimal "turnaround points" are going to be a function of x.

We can get a worst case of 3x and an average of x by following one path for a distance of x, then turning around and switching paths. This seems to go against the spirit of the question.

If we don't know the value of x then we are back to the issue of having a problem that's not well defined. This kind of reminds me of the St Petersburg paradox (the "paradox" comes from the fact that the probability distribution that's described in the question doesn't exist)
link to original post

I'm thinking it's going in a slightly different direction than that. It seems intuitive (but I could be wrong) that once you have traveled further from the origin on the path you are on than the other path, you are probably on the wrong path. But "further from the origin" starts at an infinitesimal. So you move an infinitesimal, double back, go two infinitesimals on the other path, come back and do 3, and so on, but you still haven't gone anywhere because an infinitesimal plus an infinitesimal is still an infinitesimal.

Thus I think you need some kind of finite unit to start with, or you'll never get started.

Quote: Wizard

Quote: gordonm888

You have been walking down the infinite path for some unremembered number of years when you find the Cemetery of Forgotten Books, an infinite labyrinth of rooms with shelves that contain every book ever written by humanity -whether or not it was ever published....
link to original post

That was good, thank you. May I have your permission to publish this in a book I may write on logic puzzles?
link to original post

I suppose a really evil wizard would have put this all in a Riemann elliptical space. That way you will definitely get to the portal, but whether or not you meet Sydney Sweeney first is undefined.

Quote: SkinnyTony

The answer is going to depend on the value of x.
link to original post

The answer would change if x were known. However, I claim you don't need to know x to get an answer for the general case.

As a hint, I have mentioned the uniform distribution many times. That said, when you do eventually find the portal, you may assume that any point between where you turned around your previous trip on that path and your intended goal on the current trip are all equally likely.

Example, let's on path B you last made it 10 trillion miles before you gave up and went back to path A. Then you didn't find it on path A, again, and returned with the goal of getting to 100 trillion miles on path B. Assuming you found it on that trip, you may assume the expected distance traveled that trip was 55 trillion miles.

Quote: gordonm888

proposed approach to analysis

General scheme- I will hike down one of the paths a distance a. If and when I encounter the portal, I'm done. If I don't find the portal I will return to the origin and proceed down the other path a distance b*a. If unsuccessful, I will return to the origin and proceed down the original path a distance b²a. If unsuccessful I will hike down the other path a distance b³a

Let me define
a= distance of the first hike down one of the paths

p*a = distance of the portal from the origin on one of the two paths (an unknown)

b= multiplier of the distance of the previous hike that will now be hiked on the other path (variable to be optimized)

Since p is unknown, we must write a general expression for the total distance walked as a function of a and b until we have gone a distance p down the correct path and then integrate over p from 0 to infinity to find the total "expected distance". Then we need to find the value of b that minimizes the total expected distance.

We need to do the above for two cases: 1) we start our initial hike on the correct path and 2) we start our initial hike on the incorrect path. Since these are equally probable, the optimal value of b is that which optimizes the sum (or average) of the two expected distance for the two cases.

Note an implicit assumption that we cannot see any distance ahead on the path.

link to original post