This is a discrete math (combinatorics and discrete probability) problem. Please explain e



Answered question


This issue uses discrete probability and combinatorics in mathematics. Please explain each step in detail and do not copy solutions from Chegg. 
Show that there are two numbers whose difference is a multiple of 37 in every set of 100 integers using the pigeonhole principle.  Identify the function (including its domain and target) outlined in either of our class resources while explaining how the principle is being applied.

Answer & Explanation



Skilled2021-08-16Added 89 answers

Step 1
To apply the pigeonhole principle, identify the pigeons and the pigeonholes.
Let x and y be any two integers in a set of 100 integers. If x−y is a multiple of 37, then by the division algorithm, the remainder is the set of integers from 0 to 36.
Hence, the 100 integers are the pigeons and the integers 0, 1, 2, ... , 36 are the pigeonholes.
Step 2 By the pigeonhole principle, there are two integers in the collection, which gives the same remainder when divisible by 37.
That is, x=37q1+r and y=37q2+r.
Thus, there are two integers in the collection such that their difference is a multiple of 37.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?