Problem 445

[Eventhorizon]

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

[mdean]

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

What you have looks correct.

[Eventhorizon]

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?

[TheEvil]

Yes, the identity map is always a retraction.

[Eventhorizon]

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!

[ironman353]

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.

[thundre]

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.

1839 is correct.

Problems 446 and 447 are about the same R function. You can look at them for addtional test values.

[ironman353]

thundre,
Thanks for your reply. I have checked the test values of problem 446 and 447 now.

[mdean]

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.

[Hossein]

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" ?

[jaap]

1)The problem states : "f(a,b,n) is retraction if ... " . Does it mean :" f(a,b,n) for x is retraction if ..." ?

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.

2) Suppose "the retraction for n" is known. Now, what is the definition of " the number of retractions for n" ?

You are misreading it.
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?