Interesting function
Let T = { 1 , 2 , 3 , … , 2 0 1 7 }. Let f be a function f : T × T → T such that
- f ( s , r ) = f ( r , s ) .
- For a fixed R , we have { f ( R , s ) ∣ s ∈ T } = T .
Let D = { f ( r , r ) ∣ r ∈ T } . Let a be the maximum value of D , b be the minimum value of D and c be the number of elements of D .
Find a + 2 b + c .
The answer is 4036.
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
It need not be true that "each row is a permutation of S". E.g. we could have f ( r , r ) = r , f ( r , s ) = 1 for r = s .
Note that since f ( r , r ) = r , clearly the min is 1, the max is 2017 and the image has size 2017.
Are you thinking of a different question?
Log in to reply
But according to my 2nd condition setting r=1 we get {f(1,s)):s belonging to S}=S.So {f(1,1),f(1,2)..., f(1,2017)}=S.Then row 1 is a permutation of S.Isn't it the same case for other rows or am I mistaken somewhere??!!
Log in to reply
Ah, now I see what you're saying. The formatting could be made much clearer.
Explaining my second point in more detail. Note that you haven't shown such a matrix could exist. All that you have is found some conditions for it, which doesn't violate 2017 as yet. You are still assuming that such a matrix could exist. In which case, since f ( r , r ) = r , hence clearly the min is 1, the max is 2017 and the image has size 2017.
Log in to reply
@Calvin Lin – I'm not saying that f(r,r)=r but {f(r,r)}=S.And can u pls explain what do u mean by existence of matrix?
Log in to reply
@Rajdeep Brahma – I misread the question due to the formatting. I've cleaned this up to make it clearer what you are saying.
(I used the word matrix because that's what you used in the solution.)
You have not yet proven that such a function could exist, and thus you are assuming that such a function could exist. All that you have shown it is neceesary for "each element occurs an odd number of times". To that extent, I agree that if n is even, then such a function could not exist. However, this does not prove that if n is odd, then such a function must exist.
Log in to reply
@Calvin Lin – Just as a note, the solution shows that if such a function exists and n is odd, then D = T is uniquely defined.
There always exist such functions for any positive n (e.g. f ( r , s ) = r + s ( m o d n ) , where we identify any number with its congruence class, will always give an example).
The solution doesn't apply for n even, but this isn't because such a function doesn't exist, but rather it's possible for D = T when n is even (which is exhibited by the example class I gave above).
Log in to reply
@Brian Moehring – Exactly & that's a good example.
@Calvin Lin – Thanks a lot.Now I get your question.I'll try to show it.If I can I'll let u know.
@Calvin Lin – Yeah it exists.Let the required matrix be ABCD.Along BD diagonal write 2017 in all the boxes.Above the diagonal write 2016 in all of the boxes & below write 1 in all of the boxes.Above set of boxes with no.2016 write 2015 & below the boxes with no.1 write 2.Continue like this & u'll get the desired matrix.
Take n = 2017.Arrange the values of f in a nXn matrix.Each row is a permutation of S.So each element occurs odd no. of times(since n is odd).If any no. k is missing in the diagonal then it must occur even no. of times,hence each element of S occurs once in D.(Note the matrix is symmetric wrt the diagonal as f(r,s)=f(s,r)).Hence D=S.a=2017,b=1,c=2017.So a+2b+c=2017+2+2017=4036(ANS)