Prove that any group of 20 people will contain at least one pair of people with the same a

Dottie Parra 2021-08-20 Answered
Prove that any group of 20 people will contain at least one pair of people with the same amount of friends within the group. (Here, you can let \(\displaystyle{S}={\left\lbrace{p}_{{{1}}},{p}_{{{2}}},\ldots,{p}_{{{20}}}\right\rbrace}\) be an arbitrary set of 20 people, and define \(\displaystyle{n}{\left({p}_{{{i}}}\right)}\) for \(\displaystyle{1}\leq{i}\leq{20}\) to be the number of friends for person \(\displaystyle{p}_{{{i}}}\) within this group. Assume friendship is symmetric, so if someone has 0 friends in the group then there can't be someone with 19 friends. Similarly, if someone has 19 friends in the group then there can't be anyone with 0 friends in the group. What are the possible values of \(\displaystyle{n}{\left({p}_{{{i}}}\right)}.?{)}\).

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Plainmath recommends

  • Ask your own question for free.
  • Get a detailed answer even on the hardest topics.
  • Ask an expert for a step-by-step guidance to learn to do it yourself.
Ask Question

Expert Answer

l1koV
Answered 2021-08-21 Author has 2895 answers
Step 1
We will use Pigeonhole Principle: If \(\displaystyle{n}+{1}\) objects are placed in n boxes, then one at least one box contains two objects.
There are 20 people. So, one can have a maximum of 19 friends (friend with everyone).
Step 2
So, 20 people should be put in 19 boxes for the number of friends: 1 friend, 2 friends, 3, 4, …, 19. There are 19 boxes and \(\displaystyle{19}+{1}\) objects. Therefore, by the pigeonhole principle with \(\displaystyle{n}={19}\), there is at least one box with two objects, which means, at least one number (of friends) is assigned to two people.
If one person has 0 friends, then the maximum will reduce to 18. That is, a person is friends with 18 others (excluding himself and the person with no friends). Then, \(\displaystyle{n}={18}\) and \(\displaystyle{18}+{1}={19}\) people must be assigned to 18 boxes (1, 2, 3, …, 18 friends).
If there are two people having 0 friends, then we already have these two people with same number of friends (0).
Hence, at least two of them have the same number of friends.
Have a similar question?
Ask An Expert
31
 

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Relevant Questions

asked 2021-11-16
Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place?
asked 2021-02-19
A 10 kg objectexperiences a horizontal force which causes it to accelerate at 5 \(\displaystyle\frac{{m}}{{s}^{{2}}}\), moving it a distance of 20 m, horizontally.How much work is done by the force?
A ball is connected to a rope and swung around in uniform circular motion.The tension in the rope is measured at 10 N and the radius of thecircle is 1 m. How much work is done in one revolution around the circle?
A 10 kg weight issuspended in the air by a strong cable. How much work is done, perunit time, in suspending the weight?
A 5 kg block is moved up a 30 degree incline by a force of 50 N, parallel to the incline. The coefficient of kinetic friction between the block and the incline is .25. How much work is done by the 50 N force in moving the block a distance of 10 meters? What is the total workdone on the block over the same distance?
What is the kinetic energy of a 2 kg ball that travels a distance of 50 metersin 5 seconds?
A ball is thrown vertically with a velocity of 25 m/s. How high does it go? What is its velocity when it reaches a height of 25 m?
A ball with enough speed can complete a vertical loop. With what speed must the ballenter the loop to complete a 2 m loop? (Keep in mind that the velocity of the ball is not constant throughout the loop).
asked 2021-02-25
We will now add support for register-memory ALU operations to the classic five-stage RISC pipeline. To offset this increase in complexity, all memory addressing will be restricted to register indirect (i.e., all addresses are simply a value held in a register; no offset or displacement may be added to the register value). For example, the register-memory instruction add x4, x5, (x1) means add the contents of register x5 to the contents of the memory location with address equal to the value in register x1 and put the sum in register x4. Register-register ALU operations are unchanged. The following items apply to the integer RISC pipeline:
a. List a rearranged order of the five traditional stages of the RISC pipeline that will support register-memory operations implemented exclusively by register indirect addressing.
b. Describe what new forwarding paths are needed for the rearranged pipeline by stating the source, destination, and information transferred on each needed new path.
c. For the reordered stages of the RISC pipeline, what new data hazards are created by this addressing mode? Give an instruction sequence illustrating each new hazard.
d. List all of the ways that the RISC pipeline with register-memory ALU operations can have a different instruction count for a given program than the original RISC pipeline. Give a pair of specific instruction sequences, one for the original pipeline and one for the rearranged pipeline, to illustrate each way.
Hint for (d): Give a pair of instruction sequences where the RISC pipeline has “more” instructions than the reg-mem architecture. Also give a pair of instruction sequences where the RISC pipeline has “fewer” instructions than the reg-mem architecture.
asked 2020-11-09
Consider a group of 8 people. Among them, there is one pair of twins. These 8 people are taken into two different rooms, Room A and Room B, with four people to each room. If all groups of four people are equally likely, find the probability that the twins will be sent into the same room.
asked 2021-09-01
A manufacturing machine has a 5% defect rate.
If 8 items are chosen at random, what is the probability that at least one will have a defect?
asked 2021-06-02
True or false?
a. The center of a 95% confidence interval for the population mean is a random variable.
b. A 95% confidence interval for μμ contains the sample mean with probability .95.
c. A 95% confidence interval contains 95% of the population.
d. Out of one hundred 95% confidence intervals for μμ, 95 will contain μμ.
asked 2021-05-09
A pair of speakers separated by .700 m are driven by the sameoscillator at a frequency of 690 Hz. An observer originallypositioned at one of the speakers begins to walk along a lineperpendicular to the line joining the speakers.
a. How far must the observer walk before reaching a relativemaximum in intensity?
b. How far will the observer be from the speaker when the firstrelative minimum is detected in the intensity?

Plainmath recommends

  • Ask your own question for free.
  • Get a detailed answer even on the hardest topics.
  • Ask an expert for a step-by-step guidance to learn to do it yourself.
Ask Question
...