Problem 611
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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
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.
Problem 611
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
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

 Posts: 73
 Joined: Thu Nov 03, 2016 4:32 pm
Re: Problem 611
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
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 7:52 am, edited 1 time in total.
Re: Problem 611
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]?

 Posts: 73
 Joined: Thu Nov 03, 2016 4:32 pm
Re: Problem 611
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).
(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).
Re: Problem 611
Thank you LilStalker.
I did not realise that I need to consider two and only two steps.
I did not realise that I need to consider two and only two steps.

 Posts: 5
 Joined: Sun Jul 12, 2015 9:51 pm
Re: Problem 611
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 nonzero 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.
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.

 Posts: 470
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Problem 611
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
However you should remove them completely.. 31  2 * 2 = 27
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

 Posts: 470
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Problem 611
IMO, everyone once was..
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..
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

 Posts: 10
 Joined: Tue Jan 16, 2018 9:27 pm
Re: Problem 611
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.
Re: Problem 611
[deleted]
Personally I treat "If you can't solve it, then you can't solve it!" as the most important rule.
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.
Re: Problem 611
@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.
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.

 Posts: 7
 Joined: Sun Aug 02, 2015 8:14 pm
Re: Problem 611
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.
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.
Re: Problem 611
Omg I'm losing my mind. I built the Algorithm and it works.. After 10^9 I can't compute the solution under 5 min
This is the sequence for n <= 100
5, 10, 13, 17, 20, 25, 26, 29, 34, 37, 40, 41, 45, 50, 52, 53, 58, 61, 68, 73, 74, 80, 82, 89, 90, 97, 100
I found this sequence then here https://oeis.org/A025302
And after I build the algorithm to match this sequence A025302, It doesn't match for n <= 1000......
The Hallways algorithm gives me F(1000) = 233 (Which is correct)
The sequence gives me 226.. Extra numbers being >
[0] 325 int
[1] 425 int
[2] 650 int
[3] 725 int
[4] 845 int
[5] 850 int
[6] 925 int
Please tell me. Isnt the "Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way" the correct sequence for the problem ?
Help..
This is the sequence for n <= 100
5, 10, 13, 17, 20, 25, 26, 29, 34, 37, 40, 41, 45, 50, 52, 53, 58, 61, 68, 73, 74, 80, 82, 89, 90, 97, 100
I found this sequence then here https://oeis.org/A025302
And after I build the algorithm to match this sequence A025302, It doesn't match for n <= 1000......
The Hallways algorithm gives me F(1000) = 233 (Which is correct)
The sequence gives me 226.. Extra numbers being >
[0] 325 int
[1] 425 int
[2] 650 int
[3] 725 int
[4] 845 int
[5] 850 int
[6] 925 int
Please tell me. Isnt the "Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way" the correct sequence for the problem ?
Help..
Re: Problem 611
I don't know, I haven't been paying attention if a number can be represented as the sum of 3 squares or no.. Is that the secret for this sequence ? I can't believe https://oeis.org/ doesnt have this sequence written down
Re: Problem 611
No, I mean three different ways of representing a number as the sum of two squares, then the door with this number would be opened, closed and opened again, thus this number would have to be counted as well.
Re: Problem 611
Thanks for your time, but I've given up already. I guess if https://oeis.org doesn't have it written down, its not me who's going to discover it with my lousy math skills.