1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Ksju [112]
3 years ago
8

Pigeon Hole Principle :

Mathematics
1 answer:
yaroslaw [1]3 years ago
5 0

Answer:

A proof can be as follows:

Step-by-step explanation:

Let S=\{a_{1},a_{2},...,a_{n},a_{n+1}\} be a set of n+1 integers. By the division algorithm the possible remainders when we divide by n are 0,1,2,....,n-1. Then, each integer a_{i}\in S can be written as:

a_{i}=np_{i}+r_{i},\,\,0\leq r_{i}

Observe that the set of remainders \{r_{1},r_{2},...,r_{n+1}\} has n+1 elements and each element has n possible values. By the Pigenhole principle at least two remainders have the same value. Suppose that this two elements are a_{i}, a_{j}. Then,

\begin{array}{c}a_{i}=np_{i}+r\\a_{j}=np_{j}+r\end{array}

Where r_{i}=r_{j}=r. Then,  a_{i}-a_{j}=np_{i}-np_{i}=n(p_{i}-p_{j}). Then we have that n divides a_{i}-a_{j}.

You might be interested in
50x1= what is the answer?​
mote1985 [20]

Answer: 50

Step-by-step explanation:

3 0
3 years ago
Read 2 more answers
HELP ME WITH THIS MATH
tester [92]

Answer: Do you know what the total degree is but if not an algebraic equation us 148-x = 26

Step-by-step explanation:

7 0
3 years ago
Read 2 more answers
PLEASE HELP WILL GIVE BRANLIEST IF CORRECT
nevsk [136]

Answer:

1,500,000,000

Step-by-step explanation:

6 0
2 years ago
Which measurement is equivalent to 1 pound?
DaniilM [7]

16 Ounces, I hope this helps, Mark me brainliest

6 0
2 years ago
Help please...........
Nady [450]
The answer is B.

Function means every x corresponds to one unique y value. ACD all have duplicates correspondence.
6 0
3 years ago
Read 2 more answers
Other questions:
  • A gravel company sells gravel by the cubic yard and charges a flat delivery fee. The table shows the total cost C based on the a
    13·1 answer
  • Three times a number, X, increased by four is equal to five times the number, x. Which equation can be used to solve for x?
    5·2 answers
  • The function below was generated using an equation of the form f(x) = asin(bx – c). On a coordinate plane, a function has a maxi
    14·2 answers
  • (-3x + 7) + (-6x + 9)
    5·2 answers
  • Plz help meh. In a small town in Utah, 40,000 homes used to have land-line phones. If there was a 12.5% decrease, how many homes
    9·1 answer
  • ILL GIVE BRAINLIEST
    15·1 answer
  • HELP PLS ANSWER <br> Which set of ordered pairs represents a function?
    14·2 answers
  • Please solve thank you very much!!
    15·2 answers
  • WHAT IS THE ANSWER PLEASE TELL!
    12·1 answer
  • What is a slope of a line between the x-axis and y-axis​
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!