Elevator Game

  • #1
DaveC426913
Gold Member
18,652
2,119

Main Question or Discussion Point

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 gonna 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.
 

Answers and Replies

  • #2
DaveC426913
Gold Member
18,652
2,119
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.
 
Last edited:
  • #3
DaveC426913
Gold Member
18,652
2,119
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.
 
  • #4
11,520
5,071
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.
 
  • #5
DaveC426913
Gold Member
18,652
2,119
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.
 
  • #6
11,520
5,071
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
 
  • #7
DaveC426913
Gold Member
18,652
2,119
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.
 
  • #8
11,520
5,071
yes sorry I got the sign wrong, my bad.
 
  • #9
DaveC426913
Gold Member
18,652
2,119
So, is it possible to write a formula that outputs multiple values?
(I mean, it must be. y=x^2 has multiple solutions.)
 
  • #10
11,520
5,071
if it output a vector then yes.
 
  • #11
DaveC426913
Gold Member
18,652
2,119
Yeah, I dunno how to do that.
 
  • #12
11,520
5,071
input is a number and output is a vector:

FXY(50) = <x,y>
 
  • #13
11,520
5,071
The trouble is I think this is a diophantine problem which makes it somewhat difficult.

Perhaps @fresh_42 could give some insight here.
 
  • #14
34,074
9,979
  • #15
359
109
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".
 
Last edited:
  • #16
1,945
242
  • #17
DaveC426913
Gold Member
18,652
2,119
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
 
  • #18
34,074
9,979
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.
 
  • #19
DaveC426913
Gold Member
18,652
2,119
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 thats 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.)
 
  • #20
34,074
9,979
What I described can easily be converted to a formula. Easier than finding a solution for 1 floor.
 
  • #21
OmCheeto
Gold Member
2,114
2,503
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?
 
  • #22
34,074
9,979
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'.
 
  • #23
OmCheeto
Gold Member
2,114
2,503
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.
 
  • #24
256bits
Gold Member
3,056
1,080
In the game does one floor have to be a prime number (ex 61 ).
Maybe a solution there somewhere.
 
  • #25
OmCheeto
Gold Member
2,114
2,503
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.
 

Related Threads on Elevator Game

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
2
Views
3K
  • Last Post
Replies
1
Views
565
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
21
Views
5K
Top