Problem 445
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.

 Posts: 19
 Joined: Fri Sep 23, 2011 2:16 am
Problem 445
I think I just don't get modular arithmetic! I would like to get a better understanding without spoiling this problem so I will try baby steps. Can someone verify the following chain of logic:
Consider n=12, a=10, b=3 and x=6
f(x) = (10.6 + 3) mod 12 = 63 mod 12 = 3
f(f(x)) = f(3) = (10.3 + 3) mod 12 = 33 mod 12 = 9
Conclusion: {n=12, a=10, b=3} cannot be retractive because f(f(x)) != f(x) for x=6
Consider n=12, a=10, b=3 and x=6
f(x) = (10.6 + 3) mod 12 = 63 mod 12 = 3
f(f(x)) = f(3) = (10.3 + 3) mod 12 = 33 mod 12 = 9
Conclusion: {n=12, a=10, b=3} cannot be retractive because f(f(x)) != f(x) for x=6
Re: Problem 445
What you have looks correct.Eventhorizon wrote:I think I just don't get modular arithmetic! I would like to get a better understanding without spoiling this problem so I will try baby steps. Can someone verify the following chain of logic:
Consider n=12, a=10, b=3 and x=6
f(x) = (10.6 + 3) mod 12 = 63 mod 12 = 3
f(f(x)) = f(3) = (10.3 + 3) mod 12 = 33 mod 12 = 9
Conclusion: {n=12, a=10, b=3} cannot be retractive because f(f(x)) != f(x) for x=6

 Posts: 19
 Joined: Fri Sep 23, 2011 2:16 am
Re: Problem 445
Thank you mdean. Next step (I assume the following is so trivial as not to be a spoiler) ...
a=1 and b=0 => f(x) = x mod n
x <= n, so
f(x) = x when 0 <= x < n and
f(x) = 0 when x =n
Therefore, f(f(x)) = f(x) for all integer values of x, 0 <= x <= n.
i.e. f(x) is a retraction for all sets {n, a=1, b=0}
Am I right so far?
a=1 and b=0 => f(x) = x mod n
x <= n, so
f(x) = x when 0 <= x < n and
f(x) = 0 when x =n
Therefore, f(f(x)) = f(x) for all integer values of x, 0 <= x <= n.
i.e. f(x) is a retraction for all sets {n, a=1, b=0}
Am I right so far?
Re: Problem 445
Yes, the identity map is always a retraction.

 Posts: 19
 Joined: Fri Sep 23, 2011 2:16 am
Re: Problem 445
Last step, some more interesting retractions:
{n=6, a=3, b=0} is a retraction because
f(0) = 0 => f(f(0)) = f(0) = 0 and f(2) = f(4) = 0
f(3) = 3 => f(f(3)) = f(3) = 3 and f(1) = f(5) = 3
{n=6, a=4, b=3} is a retraction because
f(0) = 0 => f(f(0)) = f(0) = 0 and f(3) = 0
f(2) = 2 => f(f(2)) = f(2) = 2 and f(5) = 2
f(4) = 4 => f(f(4)) = f(4) = 4 and f(1) = 4
So a pattern begins to emerge  I needed to work a little harder with pencil and paper!
Thanks for the replies  they helped!
{n=6, a=3, b=0} is a retraction because
f(0) = 0 => f(f(0)) = f(0) = 0 and f(2) = f(4) = 0
f(3) = 3 => f(f(3)) = f(3) = 3 and f(1) = f(5) = 3
{n=6, a=4, b=3} is a retraction because
f(0) = 0 => f(f(0)) = f(0) = 0 and f(3) = 0
f(2) = 2 => f(f(2)) = f(2) = 2 and f(5) = 2
f(4) = 4 => f(f(4)) = f(4) = 4 and f(1) = 4
So a pattern begins to emerge  I needed to work a little harder with pencil and paper!
Thanks for the replies  they helped!

 Posts: 11
 Joined: Thu Jan 16, 2014 2:29 pm
Re: Problem 445
It is given in the problem that ∑ R(c) for c=C(100 000,k), and 1 ≤ k ≤99 999 ≡628701600 (mod 1 000 000 007).
My brute force program is unable to get it. Can anyone confirm for some smaller limits?
∑ R(c) for c = 1 to c = 100 is 1839.
My brute force program is unable to get it. Can anyone confirm for some smaller limits?
∑ R(c) for c = 1 to c = 100 is 1839.
Re: Problem 445
1839 is correct.ironman353 wrote:It is given in the problem that ∑ R(c) for c=C(100 000,k), and 1 ≤ k ≤99 999 ≡628701600 (mod 1 000 000 007).
My brute force program is unable to get it. Can anyone confirm for some smaller limits?
∑ R(c) for c = 1 to c = 100 is 1839.
Problems 446 and 447 are about the same R function. You can look at them for addtional test values.

 Posts: 11
 Joined: Thu Jan 16, 2014 2:29 pm
Re: Problem 445
thundre,
Thanks for your reply. I have checked the test values of problem 446 and 447 now.
Thanks for your reply. I have checked the test values of problem 446 and 447 now.
Re: Problem 445
I can't seem to get the given result. If I replace 100,000 with 10, the answer appears to be correct. Can I pm someone this value just to confirm it's correct?
Update: Never mind. Caught a mistake for $\binom{20}3$. Found a "1" where there should have been an "i". Now I just need to figure out how to speed it up. Currently takes about 20 seconds for 100,000. 10,000,000 is going to take quite a while.
Update: Never mind. Caught a mistake for $\binom{20}3$. Found a "1" where there should have been an "i". Now I just need to figure out how to speed it up. Currently takes about 20 seconds for 100,000. 10,000,000 is going to take quite a while.
Re: Problem 445
1)The problem states : "f(a,b,n) is retraction if ... " . Does it mean :" f(a,b,n) for x is retraction if ..." ?
2) Suppose "the retraction for n" is known. Now, what is the definition of " the number of retractions for n" ?
2) Suppose "the retraction for n" is known. Now, what is the definition of " the number of retractions for n" ?
Re: Problem 445
For any a,b,n, we have a function f_{a,b,n}. It is a function of x. Being a retraction is a property of the function as a whole.Hossein wrote:1)The problem states : "f(a,b,n) is retraction if ... " . Does it mean :" f(a,b,n) for x is retraction if ..." ?
You are misreading it.Hossein wrote:2) Suppose "the retraction for n" is known. Now, what is the definition of " the number of retractions for n" ?
For a given value of n, we can choose any value of 0<=a,b<n to get a function f_{a,b,n}. There are n*n choices for these values of a,b so there are n*n of these functions. How many of them have this property of being a retraction?
_{Jaap's Puzzle Page}