Problem 611

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
henrig
Posts: 6
Joined: Mon Nov 21, 2016 7:39 am

Problem 611

Post by henrig » Sun Oct 08, 2017 5:30 am

Could someone please explain why F(5)=1 and not F(5)=3?

Is there not only two actions that Peter can take for N=5: (a) 1+4 and (b) 4. That would leave doors 1, 4 and 5 open.

I am also not sure how to deal with door zero. Is it closed for F(5) since it was opened it for 1+4 and then closed it for 4?

I would appreciate clarity on my questions.

Thank you

Henri

LilStalker
Posts: 40
Joined: Thu Nov 03, 2016 4:32 pm

Re: Problem 611

Post by LilStalker » Sun Oct 08, 2017 5:53 am

For F(5):
You only toggle the door after you do both steps (a) and (b) so (1 + 4) and you toggle the doors you are at - door number 5.
This is also the only posible action you can take. Since only door 5 is open it follows that F(5) = 1.

EDIT: (a) and (b) here have no connection with yours.
(a) move for x^2 steps
(b) move for another y^2 steps y>x
Last edited by LilStalker on Sun Oct 08, 2017 6:52 am, edited 1 time in total.
Image

henrig
Posts: 6
Joined: Mon Nov 21, 2016 7:39 am

Re: Problem 611

Post by henrig » Sun Oct 08, 2017 6:01 am

Does that not leave both doors 4 and 5 open (in which case F(5)=2)? Door 5 is open due to action (a) [1^2 + 2^2] and door 4 is open after (b) [2^2]?

LilStalker
Posts: 40
Joined: Thu Nov 03, 2016 4:32 pm

Re: Problem 611

Post by LilStalker » Sun Oct 08, 2017 6:26 am

But what happened with the step (a) in your second example? An action goes as follows:
(a) move for x^2 steps
(b) move for another y^2 steps y>x
(c) toogle the doors
(d) go back to 0

In your second example you do not do step (a).
Image

henrig
Posts: 6
Joined: Mon Nov 21, 2016 7:39 am

Re: Problem 611

Post by henrig » Sun Oct 08, 2017 8:10 am

Thank you LilStalker.

I did not realise that I need to consider two and only two steps.

TheBonobo4
Posts: 4
Joined: Sun Jul 12, 2015 8:51 pm

Re: Problem 611

Post by TheBonobo4 » Sun Oct 15, 2017 5:44 am

I've just written out all the possible moves for 100 doors. In the question it says that F(100) = 27, but I get it as 29. Have I missed something (misunderstood the question), or is this a typo? I get it as he starts at door 0, moves a positive non-zero number of steps x, then a second, positive, number of steps y, where x<y. So for F(5)=1, this is because the only move is 1,4,5 and 0,1,1 and 0,4,4 are invalid moves. Here I've written in the form x, y, x+y, (that is, door after step 1, then how many more doors he moves to get to his final door). So for F(100) I have:

F(100)=27 as claimed in the question, yet I get 29 as follows:

1,4,5
1,9,10
1,16,17
1,25,26
1,36,37
1,49,50
1,64,65
1,81,82

4,9,13
4,16,20
4,25,29
4,36,40
4,49,53
4,64,68
4,81,85

9,16,25
9,25,34
9,36,45
9,49,58
9,64,73
9,81,90

16,25,41
16,36,52
16,49,65
16,64,80
16,81,97

25,36,61
25,49,74
25,64,89

36,49,85
36,64,100

leading to 31 possible moves, with doors 65 and 85 closed as they are opened then closed, and 29 total doors open.

Also apologies if this post violates forum rules in any way, I hope this doesn't count as spoilers, I'm just asking for clarity and confirmation.
Image

MuthuVeerappanR
Posts: 319
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 611

Post by MuthuVeerappanR » Sun Oct 15, 2017 6:12 am

I think you should remove 65 and 85 twice... You are removing it only once and get 31 - 2 = 29..

However you should remove them completely.. 31 - 2 * 2 = 27
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

TheBonobo4
Posts: 4
Joined: Sun Jul 12, 2015 8:51 pm

Re: Problem 611

Post by TheBonobo4 » Sun Oct 15, 2017 6:15 am

Good point, I'm an idiot. :lol:
Image

MuthuVeerappanR
Posts: 319
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 611

Post by MuthuVeerappanR » Sun Oct 15, 2017 6:23 am

TheBonobo4 wrote:
Sun Oct 15, 2017 6:15 am
Good point, I'm an idiot. :lol:
IMO, everyone once was.. :lol:
TheBonobo4 wrote:
Sun Oct 15, 2017 6:15 am
... or is this a typo? ...
Happens very very rarely in PE... I'm not saying it has never happened. But very rarely. So whenever I guess that the question might be wrong, I immediately conclude I'm doing something wrong. And just like you did, the best way is to clarify in this forum. Happy Solving..
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

hexadoodle
Posts: 10
Joined: Tue Jan 16, 2018 9:27 pm

Re: Problem 611

Post by hexadoodle » Tue Jan 16, 2018 9:34 pm

I've made some progress on this problem, found a useful theorem and tried many approaches, but I'm stuck. Is there anyone I can PM for a nudge in the right direction? I hope this is okay to ask, I've seen it done in earlier threads.

traxex
Posts: 77
Joined: Thu Oct 19, 2017 12:30 pm

Re: Problem 611

Post by traxex » Tue Jan 16, 2018 9:57 pm

[deleted]

Personally I treat "If you can't solve it, then you can't solve it!" as the most important rule.
Last edited by traxex on Wed Jan 17, 2018 6:17 pm, edited 3 times in total.
Technically, everyone is full of himself.

User avatar
hk
Administrator
Posts: 10054
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 611

Post by hk » Wed Jan 17, 2018 11:23 am

@traxex
I saw hexadoodle's post almost the moment it was posted and (as one of the moderators of this forum) saw no reason for action.
The moderators are visiting this forum very frequently and don't hesitate to take action if needed.
Image

TexasRebel
Posts: 7
Joined: Sun Aug 02, 2015 7:14 pm

Re: Problem 611

Post by TexasRebel » Wed Feb 14, 2018 6:42 pm

Argh!
What am I missing here...

I have 10^6 solving in 10.5s, but unfortunately that projects to about a year for 10^12...

Working on a 1.2 GHz CPU... Moving to a 3+ GHz rig would only get me down to 4 months, right?

EDIT: 6.5s on the 1.2 GHz CPU... ...but I think I have one more trick up my sleeve.

Post Reply