Brain-Teaser 46: [Lifts]
From The Sunday Times, 4th February 1962 [link]
Don and Derek live on intermediate floors in neighbouring blocks of flats each provided with a lift. Neither lift is subject to direction change by users and they both travel continuously and steadily from the ground floor to the top floor and back, stopping at each floor, and waiting at the top and bottom twice as long as at other stops. During the year the number of floors in each block is increased, though not necessarily by the same number. Don, who lives on a higher floor than Derek, notices that if his lift is not on his floor, it is twice as likely to be going down when it first comes to him as it used to be. Derek makes a similar observation on his lift.
The following year each moves four floors up and they each notice that if the lift is not on his floor, it has the same likelihood of going down when it first comes to him as it had originally.
On which floors do Don and Derek live now?
This puzzle was originally published with no title.
[teaser46]
NigelR and 
S2T2 
Jim Randell 10:13 am on 14 August 2022 Permalink |
If we consider a building with n floors, numbered from 0 to (n − 1), then this is consistent with the way building floors are numbered in the UK (i.e. 0 = ground floor, 1 = first floor, 2 = second floor, etc), assuming there are no basement levels.
If I live on floor k (0 < k < (n − 1)) of an n storey building, then the lift has 2n states (= each floor × {up, down}), and (2n − 2) are not at my floor. Of these the lift will be travelling up when it arrives only if it is below my floor, i.e. in 2k states.
So the likelihood of an arriving lift going up is:
And the likelihood of it going down is:
This Python program considers building with 3 to 40 floors.
It runs in 60ms. (Internal runtime is 5.8ms).
Run: [ @replit ]
from enigma import (defaultdict, Rational, irange, unpack, subsets, printf) Q = Rational() # generate (n, k, m) values def generate(): # record probabilities of lift going down # d: down(n, k) -> (n, k) d = defaultdict(list) # n = floors of the building for n in irange(3, 40): # consider each floor for k in irange(1, n - 1): # calculate probability of lift going down p = Q(n - k - 1, n - 1) # is it the same value as the (k - 4)th floor of a lower building? # and half the value as the (k - 4)th floor in this building for (n_, k_) in d[p]: if k == k_ + 4 and n_ < n and (n, k_) in d[p * 2]: yield (n_, k_, n) # record this value d[p].append((n, k)) # collect solution values sorted by k ss = sorted(generate(), key=unpack(lambda n, k, m: k)) # choose values for Derek (lower floor) and Don (higher floor) for vs in subsets(ss, size=2): for (t, (n, k, m)) in zip(["Derek", "Don"], vs): printf("{t}: floor {k} of {n} -> floor {k} of {m} -> floor {k4} of {m}", k4=k + 4) printf()Solution: Derek lives on the eighth floor of his building. Don lives on the sixteenth floor of his building.
Derek starts on floor 4 of 7 (numbered 0 to 6). There are 4 lift states above him and 8 lift states below him, so the probability of waiting for a down lift is 4/12 = 1/3.
The building is then expanded to 13 floors, which adds 12 lift states above him, so the probability of waiting for a down lift is now 16/24 = 2/3.
So the probability of a down lift is twice what it was before.
Derek then moves up 4 floors to floor 8 of 13. There are 8 lift states above him and 16 lift states below him, so the probability of waiting for a down lift is now 8/24 = 1/3, the same as it was originally.
And Don starts on floor 12 of 16. There are 6 lift states above him, and 24 lift states below him, so the probability of waiting for a down lift is 6/30 = 1/5.
The building is then expanded to 21 floors, which adds 10 lift states above him, so the probability of waiting for a down lift is now 16/40 = 2/5.
Don then moves up 4 floors to floor 16 of 21. There are 8 lift states above him and 32 lift states below him, so the probability of waiting for a down lift is 8/40 = 1/5.
LikeLike
Jim Randell 10:16 am on 14 August 2022 Permalink |
With a bit more analysis:
When the building is extended to m floors, we are interested in situations where:
and also:
which give:
For integer values of n we need (k + 4) to be a divisor of 16.
So, Derek starts on floor 4 of (4 + 5 − 16/8) = 7, then floor 4 of (4 + 9) = 13, then floor (4 + 4) = 8 of 13.
And, Don starts on floor 12 of (12 + 5 − 16/16) = 16, then floor 12 of (12 + 9) = 21, then floor (12 + 4) = 16 of 21.
This Python program runs in 55ms. (Internal run time is 152µs).
Run: [ @replit ]
from enigma import (divisors_pairs, unpack, subsets, printf) # generate (n, k, m) values def generate(): for (k4, x) in divisors_pairs(16, every=1): k = k4 - 4 if k > 0: yield (k + 5 - x, k, k + 9) # collect solution values sorted by k ss = sorted(generate(), key=unpack(lambda n, k, m: k)) # choose values for Derek (lower floor) and Don (higher floor) for vs in subsets(ss, size=2): for (t, (n, k, m)) in zip(["Derek", "Don"], vs): printf("{t}: floor {k} of {n} -> floor {k} of {m} -> floor {k4} of {m}", k4=k + 4) printf()LikeLike
NigelR 5:41 pm on 16 August 2022 Permalink |
I took a slightly different approach but reached (I think) the same conclusion. I considered the time that the lift took from doors closing to doors opening going in each direction. The double wait at top and bottom effectively offsets the ‘dead’ time while it is at floor n and makes the maths a lot easier! Going down, the lift takes 2nt before the doors open again, where t is the combined transition and wait time for each floor. Going up, the lift takes 2(f-n)t, where f is the number of floors. Hence the probability that the lift when not visible is above floor k (ie it will arrive going downwards) is: (2(f-n)t)/2ft or (f-n)/f.
Brute force:
pdown = lambda n,f: (f-n)/f #probability that a lift is going down on arrival at floor n of a block of height f sol=[[f,n,d] for f in range(50) for n in range(1,f) for d in range(1,20) if 2*pdown(n,f) == pdown(n,f+d) and pdown(n,f) == pdown(n+4,f+d)] if len(sol) == 2: print('Don now lives on floor',sol[1][1]+4 ,'of his block and Derek is on floor',sol[0][1]+4,'of the other' ) else:print('no unique solution')By analysis, for each block with d floors added we have (f-n)/f = ((f+d)-(n+4))/(f+d) ⇒ nd=4f … (1)
We also have 2((f-n)/f) = (f+d-n)/(f+d), which ⇒ f² -fn +fd -2nd=0 … (2)
Combining (1) and (2) we get: f+d-n=8
Hence:
sol=[[f,n,(8+n-f)] for f in range(50) for n in range(1,f) if (4*f)%n==0 and int((4*f)/n)==8+n-f] if len(sol) == 2: print('Don now lives on floor',sol[1][1]+4 ,'of his block and Derek is on floor',sol[0][1]+4,'of the other' ) else:print('no unique solution')[timing] total time: 0.0005922s (592.20us)
LikeLike