These forums have been archived and are now read-only.

The new forums are live and can be found at https://forums.eveonline.com/

Out of Pod Experience

 
  • Topic is locked indefinitely.
Previous page12
 

Extra Credit Problem:
Author
Previous Topic Next Topic
Rabb Darktide
The Scope
Gallente Federation
#21 - 2011-10-21 15:46:03 UTC
Taedrin wrote:
An intriguing challenge from a friend of a friend, which a group of us already solved.

A prince from Far, Far Away visits a castle with the intention of wooing the princess there. The castle has a (straight) corridor with 17 rooms lined side-by-side. Each of the rooms have two doors connecting each other (except for the rooms on the ends), and another door connected to the corridor. A guard stops the prince and tells him that the princess is one of these rooms. However, the prince is allowed to knock on only a single door from the corridor. If the princess is in the room, he will be able to woo her and live happily ever after. If the princess is not in the room, he must leave and come back tomorrow to try again. Every night, the princess moves to an adjacent room. She never spends more than a single night in a room at a time.

Unfortunately, the prince already has his plane ticket for his return flight in 30 days. Can the prince conquer the princess? Prove your answer to be correct.



Simple.. Knock on the same door every night. If she is not there in the first night, she will be there sometime within the next 16 nights, leaving him just shy of two weeks to knock her up, have a shotgun wedding, and still catch his flight.
Gavin DeVries
JDI Industries
#22 - 2011-10-21 16:05:00 UTC
That won't actually work. Nothing says the princess has to only move in one direction. She could quite easily just flip-flop between rooms 16 and 17, always moving back to the other, while you keep knocking on room 1.

My first through would be to walk up and down the corridor calling for her, then only knock on the door where she answers, but I suspect that's not allowed.

So, question 1: can you look through the keyholes?

Question 2: can you hear, once inside a room, if an adjacent room is occupied? If yes, then it's easy. Start at room 2, and see if either rooms 1 or 3 is occupied by the princess. If yes, knock on 2 again the following night. If she was in 1, you've caught her. If she ways in 3, there's a 50% chance you caught her and a 50% chance she's now in 4. If neither 1 nor 3 was occupied the first day, move to 3 the following day, and proceed down the corridor on successive days until the adjacent room has an occupant. Any time you do, knock on the same door the following day. Eventually she'll either move into the room you've chosen that day and you win, or you'll trap her at the far end and force her to choose your room. Either way you finish before the 30 days expires.

PVP is a question with no single right answer, but a lot of wrong ones.
Taedrin
Federal Navy Academy
Gallente Federation
#23 - 2011-10-21 16:14:45 UTC
stoicfaux wrote:
If the Prince selects room #2 twice in a row, then he is guaranteed that room #1 does not contain the Princess. I think the trick is going to requiring relying on the fact that the Princess must move every night.

For example:
If the prince (M for male) selects door 2 on day 1 (T for turn,) and the Princess (F for female) happens to be in room 1. On turn two, the Princess must move to room 2. By selecting room 2 two days in a row, the Prince either catches the Princes or can guarantee that the Princess is not in room 1.

If the prince (M for male) selects door 2 on day 1 (T for turn,) and the Princess (F for female) happens to be in room 3, then by selecting room 2 again, then the princess has to move to room 4 (or she moves to room 2 and is caught.)
T M F
1: 2 3
2: 2 4 (cannot move from room 3 to room 2, so must move to room 4)
3: 3 5 (cannot move from room 4 to room 3, so must move to room 5)
...
repeat until princess is cornered in room 17.

Once the princess is guaranteed to be two rooms away in a particular direction, then the Prince will find her assuming he has enough turns left.


However, you still have to worry about being leapfrogged, but you can compensate for that by jumping back two rooms:
T M F
1: 2 4
2: 2 3
3: 3 2 (Princess just leapfrogged the Prince)
4: 1 3 (Princess must move to room 4 next turn)
5: 2 4 (Princess is now two rooms away and will be caught)
6: 3 5
The Princess must move to room 3 on turn 4, which means she's two rooms away and will be caught.

I'm mostly sure that you can always catch the princess, but I still need to work out the pattern/formula for preventing leapfrogs for the proof.



You are exactly half way there. However, you have taken a wrong turn with trying to prevent the princess from leapfrogging you.

Here's another hint: if the princess is able to leapfrog you, her location has a certain property depending upon the "turn" it is. Think evens and odds.
Taedrin
Federal Navy Academy
Gallente Federation
#24 - 2011-10-21 16:22:17 UTC
Gavin DeVries wrote:
That won't actually work. Nothing says the princess has to only move in one direction. She could quite easily just flip-flop between rooms 16 and 17, always moving back to the other, while you keep knocking on room 1.

My first through would be to walk up and down the corridor calling for her, then only knock on the door where she answers, but I suspect that's not allowed.

So, question 1: can you look through the keyholes?

Question 2: can you hear, once inside a room, if an adjacent room is occupied? If yes, then it's easy. Start at room 2, and see if either rooms 1 or 3 is occupied by the princess. If yes, knock on 2 again the following night. If she was in 1, you've caught her. If she ways in 3, there's a 50% chance you caught her and a 50% chance she's now in 4. If neither 1 nor 3 was occupied the first day, move to 3 the following day, and proceed down the corridor on successive days until the adjacent room has an occupant. Any time you do, knock on the same door the following day. Eventually she'll either move into the room you've chosen that day and you win, or you'll trap her at the far end and force her to choose your room. Either way you finish before the 30 days expires.


This is a math riddle, so no loop holes are needed to solve the problem. You can not look through keyholes, she will not respond to you if you call to her, if you destroy or damage her castle she will be quite cross with you and you will be unable to woo her, she has taken ninja classes so you will not be able to hear her nor see any evidence of her having occupied a room, etc etc...

The only important information is:

1) The 17 rooms are connected to each other, much like a "Linked List", and there are 2 ends - i.e. the rooms do not loop.
2) The princess can only move to an adjacent room
3) The princess MUST move every night
4) The prince can only check one room a day
5) The prince only has 30 chances.

The key to this problem is constraints #2 and #3, as this forces the princess's location to have one of two properties - both of which are exploitable. The question is if you do it in 30 days.
Myfanwy Heimdal
Heimdal Freight and Manufacture Inc
#25 - 2011-10-21 16:43:43 UTC
Doh! There's only one set of rooms and not two. So, one side of the corridor has no doors.

This is starting to make more sense.

Pam:  I wonder what my name means in Welsh?Nessa: Why?
Myfanwy Heimdal
Heimdal Freight and Manufacture Inc
#26 - 2011-10-21 16:45:46 UTC
Prince starts in room 1.
Next day room 2
Then room 1
Fourth day room 3
Fifth day room 2
Sixth day room 1


That sort of thing?

Pam:  I wonder what my name means in Welsh?Nessa: Why?
stoicfaux
#27 - 2011-10-21 16:49:45 UTC
Taedrin wrote:

You are exactly half way there. However, you have taken a wrong turn with trying to prevent the princess from leapfrogging you.

Here's another hint: if the princess is able to leapfrog you, her location has a certain property depending upon the "turn" it is. Think evens and odds.


I know, I know. But I'm just too brain dead to see and formalize the property. Whoever says "sleeps like a baby" to indicate peaceful sleep doesn't have kids.

Pon Farr Memorial: once every 7 years, all the carebears in high-sec must PvP or they will be temp-banned.
Rabb Darktide
The Scope
Gallente Federation
#28 - 2011-10-21 17:09:20 UTC
Gavin DeVries wrote:
That won't actually work. Nothing says the princess has to only move in one direction. She could quite easily just flip-flop between rooms 16 and 17, always moving back to the other, while you keep knocking on room 1.



Well, in that case the Prince should just find the singles bar in the castle and find a woman who doesn't want to start out the relationship by playing head games.
Rabb Darktide
The Scope
Gallente Federation
#29 - 2011-10-21 17:09:37 UTC  |  Edited by: Rabb Darktide
Stupid double post..
Karl Planck
Perkone
Caldari State
#30 - 2011-10-21 17:16:07 UTC
grrrr i nearly have it but i am over by one freaking day

I has all the eve inactivity
stoicfaux
#31 - 2011-10-21 17:20:42 UTC  |  Edited by: stoicfaux
Karl Planck wrote:
grrrr i nearly have it but i am over by one freaking day


[2..16, 16..2]?

edit: To clarify:

Check rooms in this order: 2, 3, ..., 16, 16, 15, 14, ..., 2 (16 gets checked twice in a row.)

Pon Farr Memorial: once every 7 years, all the carebears in high-sec must PvP or they will be temp-banned.
Karl Planck
Perkone
Caldari State
#32 - 2011-10-21 17:30:21 UTC
got it, started on door one instead of door 2.

OK. So here you do it.

The prince starts on door 2 and works his way every day up to door 16 (day 15). If by that day he has not found her that means she started on an odd numbered door. Otherwise he HAD to have found her. To make sure she isn't in door 17 he stays on door 16 for another day (16th day). At this point, at the very least he knows that the evenness or oddness of the days corresponds with the room she is in, and can be confident that she cannot leapfrog him. Each proceeding day he works backwards until he hits door 2 again, which would be the 30th day.

Although I do not have a general formula for this, it is impossible to miss her if this is followed.

TL;DR
Start on door 2 and work up to door 16. Stay on door 16 for an extra day then work back down to door 2.

I has all the eve inactivity
Karl Planck
Perkone
Caldari State
#33 - 2011-10-21 17:30:52 UTC
stoicfaux wrote:
Karl Planck wrote:
grrrr i nearly have it but i am over by one freaking day


[2..16, 16..2]?

edit: To clarify:

Check rooms in this order: 2, 3, ..., 16, 16, 15, 14, ..., 2 (16 gets checked twice in a row.)


lol damn, you beat me to it

I has all the eve inactivity
NeoShocker
The Dark Space Initiative
Scary Wormhole People
#34 - 2011-10-21 17:43:03 UTC  |  Edited by: NeoShocker
Since there are hardly any rules or restrictions other than picking only one door per day...

Well, thinking out of the box. I place a small piece of paper on each door if allowed, so when it opens, paper fall on the floor and you have a very good chance she is in it.

Then again, doesn't have to be each, door, but each time you choose a wrong room, place something on the door, again, like a paper. More wrong doors with something to tell you it is not used, princess is not there. Day by day for wrong chosen doors and placing objects on said doors, your chances to encounter the princess increases. If the object is on the floor by the door, your chances is very high. :)

This way, you almost cannot fail to encounter the princess.
stoicfaux
#35 - 2011-10-21 17:51:13 UTC  |  Edited by: stoicfaux
Karl Planck wrote:
stoicfaux wrote:
Karl Planck wrote:
grrrr i nearly have it but i am over by one freaking day


[2..16, 16..2]?

edit: To clarify:

Check rooms in this order: 2, 3, ..., 16, 16, 15, 14, ..., 2 (16 gets checked twice in a row.)


lol damn, you beat me to it


Nah, we both got the solution, but we don't have a good proof yet.


edit:
ARGH. After you check rooms (2..16, 16) the Princess can only be in an even numbered room (on turn 16.) So when you check rooms 15..2 the Princess is always an even number of rooms away from you, so it's impossible to be leapfrogged on the way back down to room 2.

I just can't show the proof why the initial walk up to the double check of room 16 forces evenness. [:head+wall:]

Pon Farr Memorial: once every 7 years, all the carebears in high-sec must PvP or they will be temp-banned.
Taedrin
Federal Navy Academy
Gallente Federation
#36 - 2011-10-21 20:19:44 UTC  |  Edited by: Taedrin
stoicfaux wrote:
Karl Planck wrote:
stoicfaux wrote:
Karl Planck wrote:
grrrr i nearly have it but i am over by one freaking day


[2..16, 16..2]?

edit: To clarify:

Check rooms in this order: 2, 3, ..., 16, 16, 15, 14, ..., 2 (16 gets checked twice in a row.)


lol damn, you beat me to it


Nah, we both got the solution, but we don't have a good proof yet.


edit:
ARGH. After you check rooms (2..16, 16) the Princess can only be in an even numbered room (on turn 16.) So when you check rooms 15..2 the Princess is always an even number of rooms away from you, so it's impossible to be leapfrogged on the way back down to room 2.

I just can't show the proof why the initial walk up to the double check of room 16 forces evenness. [:head+wall:]


We'll call that good enough. Technically, you don't have to even show WHY this works - you just have to show an example that guarantees the princess is found within 30 days.

The key to this problem is that princess can "spawn" in either an odd numbered room, or an even numbered room. If she starts in an odd numbered room, then she can only be in an odd numbered room on odd numbered days and even numbered rooms on even numbered days. If she starts in an even numbered room, then she can only be in an odd numbered room on even numbered days and even numbered rooms on odd numbered days.

Because we start on an even numbered room, we are on the same "track" as the princess if she starts on an even numbered room also. By pushing forward, we guarantee that we will find the princess, since there is no more than 1 odd number between any two consecutive even numbers, and no more than 1 even number between any two consecutive odd numbers. Once we reach the end and have eliminate the possibility that the princess has "spawned" an the even numbered rooms, we need to go backwards and catch the princess who could leapfrog us because she is on the odd numbered track.

We 'switch tracks' by knocking on the same door near the edge twice - so that we are now on even numbered rooms on even numbered days - the same as the princess if she "spawns" in an odd numbered room on day 1.

If we knock on doors [2..16][16..2], we will find the princess in exactly 30 days which is just i time for us to take her back home with us on the plane.

I have a few more Extra Credit Problems that I will present to you, but I'll let your brains rest from such torture for now.
Previous page12