# Superman looking for Supergirl

Superman needs to find Supergirl in a hotel room. Unfortunately, the hotel is also "super" and has 100,000 rooms arranged in a row. Each room has a door to the corridor and to the adjoining rooms. Superman needs 1 millisecond to check one room (by opening/closing corridor doors). After each check, if Supergirl was not found in that room she will move D rooms to her left or right. D can be any positive integer - it is always the same but Supermen does not know what number it is.

How many hours will Superman minimally need to guarantee finding Supergirl?

Supergirl always moves to another room if one is available at distance D. For example if she is in room #4 and D=10, she can not move left so she must move to the right to room #14, but if she is in room #100 she will randomly move to either #90 or #110. Another example would be for very large D=5 million, in which case Supergirl will always stay in same room since no available room is left or right at distance D.

b) how many room needs to be searched if hotel had billion rooms?

This problem is based on the fleas problem that I posted recently, and also on the prince and princess problem that was mentioned as similar.

Hints:

1. upper bounds on number of searches L for low number of rooms N are: L(7)=17, L(8)=23,..L(10)=35,..L(20)=151
2. find formula L(N) for sequence length (number of rooms that need to be searched at worst) based on solutions for e.g. N=6..35

We require a lemma:

For a given distance $$D$$ and number of rooms $$R = mD+n$$, there are $$n$$ sets of $$m+1$$ rooms that Supergirl could travel between, and $$D-n$$ sets of $$m$$ rooms.

Let's begin by extending my answer to the six-room version of this problem.

The reason that one trip was able to catch every possible flea-path is that, excluding the case where D=1, every flea-path had at most three boxes in it; this implied that any flea with D>1 had some box that it was guaranteed to be in on every other round.
This stops working once there are additional paths containing at least four rooms, which means that each such path creates a sub-problem that must be solved. For instance, in the seven-room case, the path [1,2,3,4,5,6,6,5,4,3,2,1,7] catches all fleas except the one jumping between boxes 1, 3, 5, and 7 - this one requires an additional [3,5,5,3] to be caught, yielding the hinted bound of 17.

We might be getting somewhere now.

What we'll need is a fast way to determine all the subproblems that a given number of rooms requires in order to be solved. While this appears to be a simple application of the lemma from the beginning of the answer, one question arises: how should we count, say, a subpath of size four that's a part of a subpath of size eight?
The answer is that we don't need to worry: the initial Case-2 pass is the only one that can knock out additional values of D, so further passes can simply use the Case-1 solution that treats an individual pair of (D,offset).
The formula we obtain is $$2R-1+\sum\limits_{D=2}^{\lfloor\frac{R-1}{3}\rfloor}(D-R\mod D)f(\lfloor\frac{R}{D}\rfloor)+(R\mod D)(f(\lfloor\frac{R}{D}\rfloor+1)$$, with $$f(k) = 2(k-2)$$ for $$k > 3$$ and $$0$$ otherwise.

We can simplify this, because

each subproblem has linear cost. This means that we can ask the question "How do the subproblems change when another room is added?"
The added room $$R+1$$ will lie on some existing path for each $$D$$ from $$2$$ to $$\lfloor\frac{R-1}{4}\rfloor$$, (increasing its cost by two,) and create a new path of size (and cost) four for each $$D$$ from then on to $$\lfloor\frac{R-1}{3}\rfloor$$. This comes out to a cost increase of $$4\lfloor\frac{R-1}{4}\rfloor-2\lfloor\frac{R-1}{3}\rfloor-2$$.
Some manipulation yields a new formula for cost: $$3+\sum\limits_{r=0}^{R-1}4\lfloor\frac{R-1}{4}\rfloor-2\lfloor\frac{R-1}{3}\rfloor$$. A routine calculation yields that as $$R$$ increases from $$12k$$ to $$12(k+1)$$, the cost increases by $$10k+[0,0,0,4,2,2,6,6,4,8,8,8]$$, with a total increase of $$120k+48$$. Solving for the polynomial with this bulk increase and adding in the correct error yields a final function of $$\frac{5}{12}R^2-R+[3,\frac{43}{12},\frac{10}{3},\frac{9}{4},\frac{13}{3},\frac{43}{12},2,\frac{43}{12},\frac{13}{3},\frac{9}{4},\frac{10}{3},\frac{43}{12}]$$.

How quickly will this strategy check 100,000 rooms?

4,166,566,671 moves (taking slightly less than seven weeks), and a billion rooms will take 416,666,665,666,666,671 moves (ten million times longer) to check by this strategy.

• Nice, that is correct answer and your number of moves is exactly same as what I get with my derived formula L(N). What is strange is that your formula does not seem to match those numbers. When I try to use it for N=100000 it result in 3,710,746,394 ( less than correct 4,166,566,671 ) and for N=7 it gives 14 ( again less than correct 17 ).
– lost
Commented Jul 24 at 9:29
• I found where I misread your formula - it does produces correct result. It is practically same as iterative formula that I first derived, before simplifying it to avoid O(R) complexity of sum. I posted below that simplified O(1) formula, but essentially they produce same result.
– lost
Commented Jul 24 at 11:41
• I've managed to explicitly derive your formula. Commented Jul 25 at 1:50

Edit: I misread the problem. I thought it was 1 million rooms, not 100,000. But the approach is still the same. I solved it for 100,000 rooms. The answer is 10,000,000.001 seconds or 3 months, 23 days, 17 hours, 46 minutes and 40.001 seconds.

If Supergirl moves to the room that superman just checked, would he know? I assume not.

The answer is 1,000,000,000.001 seconds or just under 32 years.

First, superman checks each room 1 - 2 - 3 ... Then he checks 2 - 4 - ... And 1 - 3 - ... Then he checks 3 - 6 - 9 - ... 2 - 5 - 8 - ... He does this for each number all the way up to 500,000. This covers every possible number Supergirl could be using. Except, their parity may be different. So after checking all numbers, he checks the last room twice. Now he has switched his parity. He then goes through and checks each sequence of rooms from 1 - 2 - 3 ... All the way to 500,000 - 1,000,000.

This means he has to check all 1,000,000 rooms in the various orders 500,000 times. So that is 1e6*5e5=5e11. Then he has to check 1 room twice to change the parity. So add 1. Then he has to check all 5e11 rooms again. Bringing the total to 1e12 + 1 room checks. Divided by 1000 to bring the time up to seconds and you get 1,000,000,000.001 seconds.

• You found a solution, but not minimal solution. As you can see from hint time, there is solution which is almost 300 times faster. Check your solution for N=7..10 rooms, I will edit hint to specifically list upper bound for those.
– lost
Commented Jul 23 at 8:17

While this problem was correctly answered by @Axiomatic, I will also post here my solution formula which has ~O(1) complexity.

Reason why I searched for that formula was that initially I planned hotel to have "more rooms than grains of sand on Earth", which would make R~1e19 and calculating that using ~O(R) summation formula would take too long. But later I decided to simplify problem to lower number of rooms.

Finding minimal number of searches L needed for R rooms involve solving subproblem for each D=1..R, where for each D we have D potential subsequences. So for R=9 we have following groups of rooms that girl can move among, depending on her starting room and D:
D1: 123456789
D2: 13579, 2468
D3: 147, 258, 369
D4: 159, 26, 37, 48
D5: 16,27,38,49,5
D6: 17,28,39,4,5,6
D7: 18,29,3,4,5,6,7
D8: 19,2,3,4,5,6,7,8
D9: 1,2,3,4,5,6,7,8,9

First group D1

is for classic problem where we know one optimal solution sequence ( order of rooms to open to ensure finding girl with minimal attempts in worst case) to be 23456788765432 or 2..(N-1)(N-1)..2 , which is 2*(N-2) moves if N>2.

All other groups can be solved

using same approach, so eg 13579 has N=5 and can be solved by sequence 357753. If we just append all those sequences together we will get "a" solution, but not "the" solution - it would not be optimal. We can obviously skip appending solution sequence twice if same group appears twice (like many single room groups do above). But even that does not yield optimal solution since even some of non-duplicate groups may be skipped if their solution subsequence already exist within previous total solution sequence.

For N=1

that optimization part is obvious - single numbers are bound to be present in longer sequences, so we will not append "5" on its own if it was in previous solutions.

For N=2 solution deviate slightly

it is any of following: 11,22,1x2,2x1,1xx1,2xx2,1xxx2 ... where 'x' means any door that is not 1 or 2 - in other words, if group has two rooms AB, solution is A(even number of other rooms, including zero)A or A(odd number of other rooms)B or same with A/B reversed. That means it is almost always possible to find solution sequence for N=2 among previous sequences, except maybe for group 1(N-1).

For N=3, eg group 123

solution is 22 or (using same logic as above) 2xx2 - as long as there is even number of rooms between two. So it is also almost always possible to find solution for groups of length N=3 among previous sequences.

For N>3 we generally can not

find subsequence in previous ones, because we create those subsequences in first place by taking all different combinations.

Therefore finding "optimal" solution boils down to finding how many subsequences we need to add to final solution and how many we can skip. And in general we can skip all subsequences of length 1&2, meaning we can skip adding subsequence to solution for all subgroups shorter than 4.

Based on that I derived formula for L(R) number of optimal moves (minimal number of doors to open that guarantee finding girl) based on total number of rooms R>=6, and that formula was simply doing sum across all viable values of D, adding subsequence lengths if they are longer than 2 - similar to formula posted by @Axiomatic

When I found optimal solutions for R=6..40 using formula from above, I noticed that second difference of L(R) has periodicity with period 12, where first difference is d1(R)=L(R)-L(R-1), and second difference is d2(R)=d1(R)-d1(R-1).

Based on that I was able to derived formula for L(R) that has complexity ~O(1), unlike initial formula with sum which had ~O(R):

if R<6 then L= 2*R -1 "special cases for small R"
N= (R-6)/12 "integer division"
M= (R-6)%12 "remainder"
ofs = { 0, 4, 8, 10, 16, 22, 28, 36, 44, 52, 64, 74 } "cumulative period offset"
L= N(5N+4)*12+11+M(10N+2)+ofs[M]

Formula above return exactly correct value for any R. But for my initial purpose of R~1e19 ( grains of sand...) it would be probably enough to use approximate version which is apparent from above formula:
L(R) ~ 5/12*R^2 "12 is due to period length"