Consider the possibilities
Find the number of ordered 64-tuples ( x 0 , x 1 , . . . , x 6 3 ) of positive integers such that x 0 , x 1 , . . . , x 6 3 are distinct elements of the set S = { 1 , 2 , . . . , 2 0 1 7 } and
x 0 + x 1 + 2 x 2 + 3 x 3 + … + 6 3 x 6 3
is divisible by 2 0 1 7 .
The answer can be expressed in the form b ! a ! − c ! ⋅ d , where a , b , c , and d are not necessarily all distinct integers. Enter the sum a + b + c + d .
The answer is 6048.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
my solution is slightly different from putnams official solution. i made a small mistake. i hope it can be corrected. i used this fact for any r in {1,2,...,2017} number of 63 tuples (x1,x2,...,x63) such that x1+2x2+3x3+.....+63x63=r mod(2017) is equal to the number of 63 tuples (x1,x2,...,x63) such that x1+2x2+3x3+.....+63x63=(r+1) mod(2017). this can be proved by giving a bijective map. the obvious map is (x1,x2,........,x63) going to (x1-1,x2-1,x3-1,......,x63-1) we can see that if x1+2x2+3x3+.....+63x63=r+1 mod(2017) then (x1-1)+2(x2-1)+.......+63(x63-1)= x1+2x2+3x3+.....+63x63-(1+2+.....+63)=x1+2x2+3x3+.....+63x63-2016= r mod(2017) the interesting thing about this result is it is valid for any expression like x1+2x2+3x3, or any thing like this which we obtain by removing some terms in x1+2x2+3x3+.....+63x63.
Log in to reply
Sure, this is true, but how do you incorporate x 0 into your calculation?
Log in to reply
this is the complete solution.consider the group Z/2017Z, the elements of the group are {0,1,2,......,2016}. Instead of zero i will use 2017. the elements of the group are {2017,1,2,3,........,2016}.
For any r in {1,2,...,2017} number of 63 tuples (x1,x2,...,x63) such that
x1+2x2+3x3+.....+63x63=r mod(2017) is equal to the number of 63 tuples (x1,x2,...,x63)
such that x1+2x2+3x3+.....+63x63=(r+1) mod(2017).
this can be proved by giving a bijective map. the obvious map is (x1,x2,........,x63) going to (x1-1,x2-1,x3-1,......,x63-1) we can see that if x1+2x2+3x3+.....+63x63=r+1 mod(2017) then (x1-1)+2(x2-1)+.......+63(x63-1)= x1+2x2+3x3+.....+63x63-(1+2+.....+63)=x1+2x2+3x3+.....+63x63-2016= r mod(2017)
the interesting thing about this result is it is valid for any expression like x1+2x2+3x3, or any thing like this which we obtain by removing some terms in x1+2x2+3x3+.....+63x63.
Now i will use this result to solve the problem.
The possible values x0 can take is equal to the set {2017,1,2,3,........,2016}. suppose x0=r,
we calculate the number of distinct 63 tuples (x1,x2,...,x63) such that x1+2x2+3x3+.....+63x63=(2017-r) mod(2017)
From the result i talked in the beginning of the solution this number is equal to (2017)(2017-1)(2017-2)........(2017-62))/2017=(2017-1)x........x(2017-62)
But in these solutions there may be some solutions where xi=r for some index i in {1,2,...,63} number of distinct 63-tuples (x1,x2,...,x63) such that r+x1+2x2+3x3+.....+63x63 is divisible by 2017 and there no index i in {1,2,...63} such that xi=r is equal to
(2017-1)x........x(2017-62)- Number of 63 tuples (x1,x2,...,x63) such that x1+2x2+3x3+.....+63x63= (2017-r)mod(2017)and xi=r for some index i in {1,2,...,63}
to calculate this we define T(p)=no of 63 tuples (x1,x2,...,x63) such that x1+2x2+3x3+.....+63x63=(2017-r) mod(2017) and there are exactly 63-p indices k1,k2,....k63-p in {1,2,....,63} such that x k1=x k2=......=x_k63-p=r and the remaining p elements in the set {x1,x2,.......,x63} are all distinct.
Now T(p+1)= (63 choose p+1) (2017-1)x.......x(2017-p)-(63-p)T(p) this is simple enumerative combinatorics Here T(1)=0 (this follows from the definition of T(r))
so when x0=r there are T(63) solutions. x0 can take 2017 values.
so the total number of solutions is equal to 2017T(63) which we can by solving the recurrence relation
here x1,x2,.....,x63 are distinct elements.
Putnam 2017, B6