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
Find the value of the expression m − 4.6 for m = 7.
stich3 [128]

Answer:

2.4

Step-by-step explanation:

If you replace m with 7, the expression is now 7-4.6.

7-4.6=2.4

The value of the expression is 2.4.

-hope it helps

3 0
2 years ago
Subtract 1/4w+4 from 1/2w+3.<br><br> A. −14w+7<br><br> B. −14w+1<br><br> C. 14w+7<br><br> D. 14w−1
frozen [14]
Im going with B) -14w+1
3 0
3 years ago
Read 2 more answers
sasha needs an average of 30 points to move to the next level in her competion . her scores in the first three events are 28, 35
salantis [7]
Sarah will need 27pts her lowest score
3 0
3 years ago
Ages Number of students
Doss [256]

Answer:

35 is the answer

Step-by-step explanation:

4 0
2 years ago
R/12=1 9/10<br><br> Solve for R.
Marianna [84]
Let's first turn 1 9/10 into an improper fraction, which is 19/10

so if R/12 equa;s 19/10, cross multiply

10r equals 228

divide both sides by 10, you get r= 22.8
7 0
2 years ago
Other questions:
  • What is the greatest common factor of 8 and 52
    5·2 answers
  • Please help! • all numbered streets runs parallel to each other. both 3rd and 4th streets are intersected by King Ave. as shown
    10·1 answer
  • Can someone help me solve for X?
    14·2 answers
  • Does the graph show a proportional relationship? explain. ​
    15·1 answer
  • What is the equation of the following line written in slope-intercept form?
    15·2 answers
  • Consider the equations: y = 2x − 2 and y = 3x − 2.
    8·2 answers
  • At a college, 72% of courses have final exams and 46% of courses require research papers. Suppose that 32% of courses have a res
    9·1 answer
  • What is 14 1/4 - 13 5/6 =
    6·1 answer
  • How to solve this problem 15 = 5x
    5·1 answer
  • Please help me i am struggling with math
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!