B Solving Elevator Game: A Formula for Any Params

[DaveC426913]

My friend has asked me for a formula that will solve his kid's elevator game.

Imagine an apartment building with an infinite number of floors, both + and -.
You start on an arbitrary floor, say 11.
The game asks you to meet your mother on the 61st floor (the actual goal floor changes).
But the elevator is broken so pressing UP will go up 61 floors (changes with each game).
And pressing DOWN will go down 18 floors (also changes).I'll generalize it for any game parameters - after I figure it out for the example parameters.

Here's my formula for this game's params:

61x - 18y = z

Where x is the number of UPs,
y is the number of DOWNs
and z is the trip desired (number of floors to move).
z is 61 -11, so that's +50.

I can move things around till I get a proper function.
61x - 18y = 50
-18y = 50 - 61x
y = (50 - 61x)/18

This gives me a line graph. But I'm missing a second formula to sub in for x or y, to give me a point.

BTW, I worked it out by brute force, solving the equation for increasing values of x, until I reached a value of y that is an integer. (Not as hard as all that: x has to be even, and it's going to be more than 6 or so. I only had to get from 6 to 20 in even increments.)

20 UPs and 65 DOWNs will move the car up by 50 floors to mom's place.

Anyway, I'm missing that substitution formula. It's got to be the ratio of 18 to 61.

 

[DaveC426913]

Ah. I think it must be x = 18/61y.

[EDIT] No, that's not right...

And besides, it can't result in a single answer, since there are multiple possible solutions. We'd be interested in the smallest, but a simple formula of the form 'y=...' isn't going to divulge that.

Is it possible this can't be solved with a formula? It would have to output an unlimited number of solutions.

 

[DaveC426913]

This my general algorithm:

Dx - Uy = z'-z

Where
D is the number of floors a single push of DOWN goes,
U is the number of floors a single push of UP goes,
x is the number of required DOWN pushes,
y is the number of required UP pushes,
z is the end floor.
z' is the start floor.

Solve for increasing values of x, until y is an integer.

But that's not a formula.

 

[jedishrfu]

Is this like hailstone numbers?

They use a different rule though if the number is even divide by 2 but if the number is odd multiply by 3 and add 1. Starting at any number you get this up/down sequence of numbers that eventually terminates at 1.

In any event, for your game you establish some "beats" like up-down or up-down-down ... and construct a list of deltas to choose from. However, I probably don't know what I'm talking about.

 

[DaveC426913]

Is this like hailstone numbers?

They use a different rule though if the number is even divide by 2 but if the number is odd multiply by 3 and add 1. Starting at any number you get this up/down sequence of numbers that eventually terminates at 1.

No. But I've played that game.
Solved it up to about 100.
Something very special about 27. It takes a ridiculously long time to reach 1.

In any event, for your game you establish some "beats" like up-down or up-down-down ... and construct a list of deltas to choose from. However, I probably don't know what I'm talking about.

I thought about that.
61-(18*3) = 7
61-(18*4) = -11
etc.
But I think that results in a tedious algorithm.

 

[jedishrfu]

Hmm so floor delta = x*ups + y*downs

50 = 61*x - 18*y ==> (61*x - 50)/18 = y with the constraint that x, y are integers.

So it seems if x starts as an integer say x=1 then y will be a rational number so you need to find an n such that ny is an integer.

Say x=1 but y=0.02 then n=50 making x=50 and y=1

EDITTED to fix sign mistake

 

[DaveC426913]

Hmm so floor delta = x*ups + y*downs

50 = 61*x + 18*y ==> (50 - 61*x)/18 = y with the constraint that x, y are integers.

Yup. That's exactly what I got. (except it should be - 18*y)
But it's an algorithm, not a formula - i,.e. it must be solved iteratively.

 

[jedishrfu]

yes sorry I got the sign wrong, my bad.

 

[DaveC426913]

So, is it possible to write a formula that outputs multiple values?
(I mean, it must be. y=x^2 has multiple solutions.)

 

[jedishrfu]

if it output a vector then yes.

 

[DaveC426913]

Yeah, I don't know how to do that.

 

[jedishrfu]

input is a number and output is a vector:

FXY(50) = <x,y>

 

[jedishrfu]

The trouble is I think this is a diophantine problem which makes it somewhat difficult.

Perhaps @fresh_42 could give some insight here.

 

[mfb]

Take the stairs?

The Chinese remainder theorem will help to find a solution.

 

[hmmm27]

Well... I can't offer a positive solution but, for starters...

The (unary disallowed) common divisors of the Up and Down values is a subset of the divisors of the Distance. Otherwise "you can't get there from here".

 

[willem2]

There isn't a simple formula, but you can use the results of the steps of the euclidean algorithm for the greatest common divisor to solve the equation.
https://www.math.uh.edu/~minru/number/hj02cs01.pdf
or

 

[DaveC426913]

There isn't a simple formula, but you can use the results of the steps of the euclidean algorithm for the greatest common divisor to solve the equation.
https://www.math.uh.edu/~minru/number/hj02cs01.pdf
or

Cool. Thanks. Who'da thunk a kid's video game could require such advanced math...Hm. I'm not sure how to deal with the fact that my equation doesn't equal 1. It equals 50:

61U - 18D = 50

 

[mfb]

If you figure out how to move by 1 floor you can also move by 50 floors: Multiply both sides by 50, then (optional) subtract 18 U and 61 D until you reach the minimal number of steps.

 

[DaveC426913]

If you figure out how to move by 1 floor you can also move by 50 floors: Multiply both sides by 50, then (optional) subtract 18 U and 61 D until you reach the minimal number of steps.

Sure, but that's back to an iterative approach. I've already got that solution. I was looking to meet the letter of my friend's request, which was a formula.
(Although I guess, solving a Diophantine formula is iterative anyway.)

 

[mfb]

What I described can easily be converted to a formula. Easier than finding a solution for 1 floor.

 

[OmCheeto]

What I described can easily be converted to a formula. Easier than finding a solution for 1 floor.

What does your formula yield if the initial conditions has no solution?

Imagine an apartment building with an infinite number of floors, both + and -.
You start on an arbitrary floor, say 12.
The game asks you to meet your mother on the 61st floor (the actual goal floor changes).
But the elevator is broken so pressing UP will go up 62 floors (changes with each game).
And pressing DOWN will go down 18 floors (also changes).

These conditions leave you always 1 floor away from your destination.
Does "you're going to have to take the stairs" come up as a fraction?

 

[mfb]

What does your formula yield if the initial conditions has no solution?

The same as an addition if there is no addition: It doesn't apply.

If nU+mD=1 and n,m>=0 and U>0, D<0 you can find n',m'>=0 such that n'U+m'D=x and n' < -D for x=1 to U and you can write down a closed formula to find n', m'.

 

[OmCheeto]

The same as an addition if there is no addition: It doesn't apply.

If nU+mD=1 and n,m>=0 and U>0, D<0 you can find n',m'>=0 such that n'U+m'D=x and n' < -D for x=1 to U and you can write down a closed formula to find n', m'.

I think this is why I seldom* post in the Maths forums.
Even in "General Math" with a "B" tag, I get completely lost.

--------------------
*33 posts in 18 threads in 11 years, afaict.

 

[256bits]

In the game does one floor have to be a prime number (ex 61 ).
Maybe a solution there somewhere.

 

[OmCheeto]

In the game does one floor have to be a prime number (ex 61 ).
Maybe a solution there somewhere.

I don't think so.
I think the only restriction on floors is that they cannot equal each other.

I'm hesitant to write down more restrictions, as it seems that every time I work on this problem, another pattern or rule pops out.

For instance, in the game when
Start = 12
Finish = 61
Up = x
Down = 18

The values for UP that yield solutions were all prime numbers, until I got to 25.
So I entered all values up to 100, and found that only primes and products of primes yielded solutions.
EXCEPT for 2 and 3.
I believe it is the fact that 2 and 3 are factors of 18 which excludes them. (18 = 2*3*3)

5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97
where:
25=5*5
35=5*7
49=7*7
55=5*11
65=5*13
77=7*11
85=5*17
95=5*19

Anyways, I looked through mfb's suggestion: Chinese Remainder Theorem, where I found Generalization to non-coprime moduli, which references Bézout's identity. Which looks like it might be what we are looking for.
Although, it says there;

"When one pair of Bézout coefficients (x, y) has been computed (e.g., using extended Euclidean algorithm), all pairs can be represented in the form [blah blah blah]..."​

So, I'm sure I have at least a few more days of studying before I figure this out.

Btw, I previously ran across this tutorial: The Euclidean Algorithm and Diophantine Equations
and decided that I do not like the Euclidean Algorithm. Most probably because it hurt my brain working through it, and it did not yield a result to Dave's problem. At least, that I could figure out. I may have to go back and restudy that also.

... n,m>=0 ...

What does that mean?

ps. Fun problem! Thanks, Dave! Gives me something to do on a rainy day.

 

[Rada Demorn]

25 posts for a single problem!

Solutions exist because 1 divides 50!

Read this https://brilliant.org/wiki/linear-diophantine-equations-one-equation/ and find the answer...

 

[mfb]

What does that mean?

It means n and m are at least zero (i.e. not negative).

There is always a solution if the greatest common divisor is a divisor of the difference between initial and final floor.

If you want to go up by 49 floors and you can go down by 18 then "up" should not share any divisors with 18=2*3*3. All prime numbers larger than 3 and their products and powers work.