Tomi's Challenges - #17

Probability Level 4

Let f : Z → Z f:\mathbb{Z}\rightarrow\mathbb{Z} be a bijective function whose (smallest) domain is [ − 5 , 5 ] [-5, 5] and whose codomain is [ − 2021 , 2021 ] [-2021, 2021] , and let g : Z → Z g:\mathbb{Z}\rightarrow\mathbb{Z} be a function whose domain is [ − 2021 , 2021 ] [-2021, 2021] , and whose image is [ − 4 , 5 ] [-4, 5] . How many functions h = ( g ∘ f ) h=(g\circ f) are there?

Note: The smallest domain here is the domain of definition. It's the analogue for the image in terms of the codomain - the image is the codomain of definition.


The answer is 199584000.

Tomislav Franov by Tomislav Franov , 17, Croatia

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

Tomislav Franov
May 14, 2021

h h is a function whose domain is [ − 5 , 5 ] [-5, 5] and whose image is [ − 4 , 5 ] [-4, 5] . How we got from the domain to the image is irrelevant, as long as the way we got from one to another is well-defined. f f is a bijection and it maps 11 11 elements to 11 11 elements, and g g is a surjection which maps these 11 11 elements to 10 10 elements. This means that every element is mapped in a well-defined way, which wouldn't be the case if for example f f mapped 11 11 elements to 2 2 elements, and the image of g g has 10 10 elements.

This means that we need to count the number of functions h : Z → Z h:\mathbb{Z}\rightarrow\mathbb{Z} whose smallest domain is [ − 5 , 5 ] [-5, 5] and whose smallest codomain (image) is [ − 4 , 5 ] [-4, 5] . This function maps 11 11 elements to 10 10 elements so, by the Pigeonhole principle, there is 1 1 element in the codomain which will receive an element 2 2 times. This means that h h is a surjection. We can choose two elements with the same image 11 C 2 11C2 ways, and we can choose where each element will get mapped 10 ! 10! ways. So in total there are 11 C 2 ⋅ 10 ! 11C2\cdot10! such functions.

2 Helpful 1 Interesting 1 Brilliant 0 Confused

Creative Problem :). However, please do have a look at the following:- Let {a1,a2,....a11} be the elements to be mapped, and let {b1,b2,....b10} be the images. In one case we can consider a11 to be the element mapped to an already mapped position, say, a10's, and let rest of the a(n) be mapped to b(n). Then a10 and a11 both have images b10. In another case we can consider a10 to be the element mapped to an already mapped position, say, a11's, and let rest of the a(n) be mapped to b(n). Again, we find a10 and a11 to be mapped to b10. (rest are the same) These 2 separate cases (according to the solution) yield the same output. It would be helpful if you would consider this, since I got the answer as 11C2x10! which is exactly half of yours. I used this approach:- There are 11C2 ways of selecting a pair of elements with the same image, and now we put this pair in a box and the other 9 elements all in separate boxes. Now these 10 boxes are filled with 10 images in 10! ways yielding an answer of 11C2x10!. Please correct me if I'm wrong :).

Deepankur Jain - 2 weeks ago

Log in to reply

Yep, you're right. I counted everything twice.. Thanks for the insight! :D I will report the problem so the Brilliant staff could change the answer.

Tomislav Franov - 2 weeks ago

Log in to reply

Right then. 👍

Deepankur Jain - 1 week, 6 days ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...