# Recursive Doors and Deluders Puzzle

You start off with $$\1.$$ You are faced with $$20$$ doors, and in front of $$10$$ each are lying lookouts and honest guards. If you enter and completely walk through a door guarded by an honest hombre, you double your money; nothing happens if you slip past a conman. You cannot retrace your steps.

However, you are in a magical palace, where each door leads to a new, slightly different room. Let $$(x, y)$$ denote a room with $$x$$ liars and $$y$$ honest mens o that you start off at $$(10, 10).$$ Exiting through a liars door denotes the shift $$(x,y) \to (x-1, y)$$ while walking through a frank frame denotes the shift $$(x,y) \to (x,y-1).$$ In other words, you end up with a room with one less door, a person of the kind you passed by having been removed. The doors are also randomly shuffled, so you cannot assume anything about them a priori as you enter/exit.

Once you end up at the final room, you have merely one guarded door left, which ostensibly leads to The Accountant's Office. Fred hates visitors and has been grumpy ever since moving in, so he bills you on the spot for $$\c^q,$$ where $$q$$ is the total number of questions you addressed to the guards along your journey and $$c$$ is a predetermined constant. Note that each question can only be addressed to one guard, and that each guard knows how the other guards behave.

For this riddle, I have prepared a set of questions ranging in difficulty, so that every puzzler may try their hand at analyzing this scenario. For the easy riddles, note that only one door leads into a room no matter how many exits it has.

Extremely easy: Explain this quote: "Fred hates visitors and has been grumpy ever since moving in..."

Very easy: assuming you may only enter the office by starting and proceeding in the aforementioned manner, and allowing an extra door for Fred to exit/enter, how many doors are connected to his office?

Easy: how many total doors are in the palace, assuming that only doors we may encounter count? Do not count Fred's secret escape hatch!

Medium: "Hi! Billy Mays here with the new mighty savings season. Call now and you can participate in this contest with $$c=0.$$" Despite the questions not costing anything, you're still impatient, so you want to get through the fortress as fast as possible. What's the minimum number of questions you need in order to nab the maximum prize?

Hard: Frank Lank the Gedankedank wants revenge since I didn't include him in the rest of the puzzle; he plans to really ramp up the costs. To top it off, he adds a $$10$$ cent tax after you walk through every door, but before you might potentially double. What is the minimum value of $$c$$ that ensures that you cannot guarantee a positive profit?

• Are you meaning that rooms have 1 entrance and multiple exits, or that each room only has 1 true exit and multiple fake exits? – Dorrulf Nov 13 '18 at 0:54
• @Dorrulf Each room only has 1 entrance, but it can have multiple exits from your perspective. I suppose I should define an exit as when you are leaving a room (through a door), and an entrance as when you are entering a room. – Display name Nov 13 '18 at 1:15
• Two important details: 1. Since the puzzle doesn't place any constraints, are the questions and answers free-form? 2. Do the guards know about other rooms' guards too? – Bass Nov 13 '18 at 6:58

If below limits/inhibits access to others or any such issue, let me know and I'll fix it up.

Hard:

Please note, I don't know how to do some notation. Hopefully my meaning is clear. I apologize in advance for incorrect notation.
1. Due to the taxes affecting the potential growth through each room, you must pass through all the doubling doors first. To do so requires a determinant path, and thus requires at least 1 question per room until all the doubling rooms are done. Note: As we are trying to find the smallest c, we must content with the smallest possible q.
2. As such, q will be equal to the number of y rooms, in this case 10.
3. The total penalty by the time you finish the just the y rooms will be:
yEn .10*2^n (summation)
Let's call this p.
4. With that, the max potential earnings by the time the y rooms are completed is:
1*2^n - p
5. We still need to factor in the losses incurred by completing all the x rooms, changing the formula to:
1*2^n - p - x*.10
or t
6. Fred only needs to charge you enough to set you back to your starting amount, in this case 1, as a gain of 0 is not a gain. This looks like:
1 = t - c^y - x*.10
or
c^y = t - x*.10 - 1
or
c = (t - 1 - x*.10)^(1/y)
8. As y and x are specified, we can now solve for c, giving us the minimum c necessary:
c = (818.4 - 1 - 1)^(.1) ~= 1.9551959979

P.S. Apologies for so many edits. Struggling with math today apparently.

Medium:

As far as I can tell, as there is no penalty for taking a liar's door, and because of the loss of an individual of the same type, you'll end up traversing through 10 liar's doors and 10 truth teller doors no matter what. And again, because of the lack of penalty, the order doesn't matter. Therefore, no questions are needed and my answer is:
0 questions

Easy:

Depending on the setup of the doors, I think it's either:
20! (Factorial) = 2,432,902,008,176,640,000
or
20? or 20E0 = 210

Very Easy:

As each initial path ends with 1 door, only those paths matter. Adding in the hatch leaves us with:
21 doors.

Extremely Easy:

I mean, he lives in the room that all paths lead to, thus the one room (other than the starting room) that every visitor will encounter. I think I'm just missing something here.

• That's not what I meant by entry; you can post solutions to any non-empty subset of the questions. My goal in having all of these questions was to allow anyone to reasonably complete some section of the puzzle. Also, I think you meant $10$ rather than $y$ since $y$ was just a free variable in the problem statement used to explain the transitions. – Display name Nov 13 '18 at 0:14
• The answer to the medium puzzle is correct. Note that only one door leads into a room no matter how many exits it has, so you didn't get the easy puzzles. The original description regarding the maze could've been confusing, so I replaced it with that equivalent aforementioned description. – Display name Nov 13 '18 at 0:43
• To clarify then @Displayname, is my answer to hard incorrect? Could you point out where I made a mistake so that I can learn and fix it :) I can try cleaning it up more if you'd like. – Dorrulf Nov 14 '18 at 20:30
• You have the hard problem correct (except the number 818.4 in the last expression is supposed to be 819.4) now. I think that you had it correct all along but I didn't notice. Anyways, I'll accept this answer. – Display name Nov 14 '18 at 22:12

## Easy:

Assuming that each door leads directly into the next with no corridor (which would add an extra door per room), and that the first room does not have a separate entrance (for which, add 1 more) then the following pattern should hold:

The first room has 20 exit doors
These lead to 20 rooms, each with 19 more doors. 20*19 = 380 exit doors (Total so far: 400 doors)
These each lead into rooms with 18 doors. 380*18 = 6,840 exit doors (Total so far: 7,240 doors)

Once we reach the 20th room on a path, we have

1 door per room, and 20! rooms. 1*(20!) = 2,432,902,008,180,000,000 exit doors

Plus the 1 for Fred to enter/leave his office, meaning a grand total of

6,613,313,319,255,706,001 doors in the palace

## Extremely easy:

If you assume each door plus frame and section of wall is 1 meter wide, then

Fred's office has a perimeter of at least 6,613,313,319,255,706,001 meters - over 3,000,000 times the perimeter of the entire USA, or 1,500,000 times the circumference of the Earth!
Forget "visitors", he'll be getting immigrants!

I sure hope his desk is near the door ;)

## Hard

To reword the question, we want the minimum value of $$C$$, such that $$C^q$$ is greater than the greatest possible result you can achieve.

Since the $0.10 is removed before the doubling, we want to double as many times as possible, as early as possible (i.e. in the first 10 rooms) This gives us the following table: Rooms : Money 0 : $$10.0$$ 1 :$ 19.8
2 : $$39.4$$
3 : $78.6 4 : $$157.0$$ 5 :$ 313.8
6 : $$627.4$$
7 : $1254.6 8 : $$2509.0$$ 9 :$ 5017.8
10 : $$10035.4$$ (Last "win")
11 : $10035.3 (These rooms all cost$0.1)
12 : $$10035.2$$
13 : $10035.1 14 : $$10035.0$$ 15 :$ 10034.9
16 : $$10034.8$$
17 : $10034.7 18 : $$10034.6$$ 19 :$ 10034.5
20 : \$ 10034.4

Now, we will discount the "lucky" case where you achieve the above with 0 questions (since $$C^0 = 1$$ for any value of $$C$$)

Thus, for any value of $$q$$, such that $$q>0$$, the minimum value of $$C$$ to ensure that you leave with no money is

$$\log _{10034.4} q$$

Bonus: Since for Hard we want to pass through all of the Easy doors first to maximize profit, the following question will always find an Honest door...

"Since some of you tell the truth, and others tell lies, which of the other guards will tell the same as you?"
For the first 9 rooms, everyone will list the Honest guards. In the 10th room, the Honest guard would say "none of them" and the Lying guards would indicate the Honest guard.

• I haven't fully verified your reasoning for the hard puzzle, but the easy ones are covered and Dorrulf got the medium puzzle, so I will accept this answer. I also upvoted both of you for the effort. Sorry for the delay. – Display name Nov 14 '18 at 20:09
• Nevermind. I just noticed that you messed up the starting amounts; try to fix that. Also, the expression involving the logarithm is wrong. – Display name Nov 14 '18 at 20:15
• However, you are very close, so I'm sure that you can get the right answer once you fix those errors. – Display name Nov 14 '18 at 20:23

Allright, I get it. So, the mansion is not a square, but rather an ever-expanding pyramid, and 10 liars' doors from the first room lead to different geographically, although, completely same effectively rooms (a waste of space it is!) Imagine it as going from 20th floor to 19th floor with 20 rooms, for easier counting.

In that formulation, we can solve the geographical conundrums:

Very Easy:

Rooms on the n-th floor have n exiting doors each. By inductuon, we can prove that n-th floor contains 20!/n! rooms (1, 20, 20*19 and so on). The first floor will contain 20! rooms, all leading with a single door to the Fred's basement.
Adding 1 escape hatch for Fred will leave us with 2432902008176640001 doors to watch over for Fred. For more comprehension, locking each of these doors (if it takes a second to lock the door) without sleeping or anything, would have taken Fred slightly more than 77 billion years.

Easy:

Each room has one entrance, so we need: amount of all rooms, minus first unenterable room, plus 20! for doors into the basement.
That would be 20!+20!/1!+20!/2!+...+20!/19! While I'm not into counting it fair and square, there's a nice approximation due to constant e=(1/1!+1/2!+... into infinity). Thus we know x = 20!e-(20!/20!)-[something really small]; count
20! + 6613313319248080001.049... - 1 - srs = 9046215327424720000 doors. That's like, 270 billion years of work for checking the doors (also, imagine size of this amount of guards' wage).

No ideas on hard or extremely easy as of now.

• This is too late (every question has already been answered), but I would've accepted anything regarding how hard of a job Fred has for the extremely easy puzzle, so you got it. – Display name Nov 28 '18 at 22:32

Very easy

Not counting Fred's own door, since every door to his office is the endpoint of a path to the final room, so there are as many doors as there are paths to the final room (actually, as many as there are paths to Fred's room, because there's only one door from the final room to Fred's room). Now to count the number of paths to Fred's room: it requires passing through 10 liars and 10 honest guards, so 10 moves of type (x,y) to (x,y-1) (down) and 10 moves of type (x,y) to (x-1,y) (left). Now, if I have understood correctly, we have to count the move from the configuration (x,y) to the configuration (x-1,y) (for example) x times in order to account for the x different liars each of whose doors leads to a different room and is hence on a different path. So because at every step of the way x is decremented by one and y remains the same, or y is decremented by one and x remains the same, we get 10*9*...*1 for x and the same thing for y. We have to multiply this by the number of ways we can get from (10,10) to (0,0) going left and down, which is $$\binom{20}{10}$$ (number of ways to place 10 left moves at 20 possible steps, the rest of the steps being filled by down moves). So all in all, $$\binom{20}{10}(10!)^2 = 20!$$. Add 1 for Fred's own door.

Easy (my solution seems a little too easy tbh!)

In the first room we see 20 doors and we go through one of these to get to the second room where there are 19 doors. We go through one of these and next we see 18 doors.. up until the last room in which there is only one door left. So we encounter a total of 20+19+...+1, or 210 doors getting to Fred's office.