1
$\begingroup$

Work shown below.

"Suppose that the numbers 1 ,2 ,3 ,…,12 are randomly distributed around a circle. Prove or disprove each of the following assertions:

a) There must be three neighbors whose sum is at least 20.

b) There must be three neighbors whose sum is at most 19.

c) There must be three neighbors whose sum is at least 22.

d) There must be four neighbors whose sum is at least 27 and four neighbors whose sum is at most 25."

So I'm relatively new to the idea of the Pigeon Hole Principle. I did some other practice questions that involved something similar, however it was about pairs that added up to 12 when 7 random numbers were selected from the numbers 1 through 11.

What I did in that case was pair up numbers that satisfied the condition "you can add them to get 12" like so: (1,11),(2,10),(3,9),(4,8),(5,7,),(6). Then, I started picking 7 numbers that wouldn't add up to 12 right away: 1,2,3,4,5,6,11. Since I was forced to pick 11, and I had already picked 1, there was necessarily a pair that gave me back 12.

Okay, so with the questions above - a), b), c), and d) - there are 3 numbers I have to work with, and it's not as simple as pairing up numbers to make groups of the form (a,b,c) since if I use 3 numbers, I get a lot more permutations - and not to mention repetition within the (a,b,c).

Is there an easy way to solve this problem, or am I supposed to just slug through it and find triplets of the form (a,b,c), like what I did above in the practice question?

I was thinking I could also use a counterproof, but I don't know where to begin for that.

|cite|improve this question
$\endgroup$
0
$\begingroup$

Hint: a)what is the sum of all the numbers? If you split the twelve numbers into four groups of three, the sum of the four groups is the sum of all twelve. b)if you subtract every number in the circle from 13, can you make use of a? c) seems easy to disprove-can you find a configuration that violates it (but I haven't tried) d) for this to fail, every group of four would have to sum to 26 (why?) If you start with a configuration where there are three disjoint groups of four numbers that each sum to 26, move the boundaries one space around the circle....

|cite|improve this answer
$\endgroup$
  • $\begingroup$ For part a), did you mean the sum of all of the numbers? (i.e. 1+2+3+4+5...+12=78)? I'm not the best at visualizing things, so how would knowing the sum of all the numbers help me? If I took 78 and broke it back into 4 parts (made up of 3 "neighbour numbers" each), then those sums would give me 19.5, which is below 20, but I wouldn't be able to use this to say there aren't any neighbours whose sum is at least 20 because the decimal answer implies that I'm working with fractions and not the whole numbers 1,2,3,...12. $\endgroup$ – Questioneer Jan 3 '15 at 22:22
  • $\begingroup$ Yes. If all four groups of three were at most $19$, the total would be at most $76$, so at least one group of three is at least $20$ $\endgroup$ – Ross Millikan Jan 3 '15 at 22:25
  • $\begingroup$ Ah, okay. I should slap my forehead for that one. Thanks. $\endgroup$ – Questioneer Jan 4 '15 at 4:38
0
$\begingroup$

Usually, when you're working with pigeon hole, you've to found the right thing you apply this priciple to.

In this case, you only want to know the bounds for the sum of numbers in a triplet(or 4). If you take a casual configuration, what is the sum of this value for all the triples in your configuration? What does this sum tells to you?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This answer seems unhelpful to me. Perhaps it is relevant to case (b), but not any of the others. $\endgroup$ – TonyK Jan 3 '15 at 20:55
  • $\begingroup$ it helps in a) b) d). Only c) requires something more $\endgroup$ – Exodd Jan 3 '15 at 20:55
  • $\begingroup$ Yes, sorry, you are right about (a). But (d) also requires something more. $\endgroup$ – TonyK Jan 3 '15 at 20:59
  • $\begingroup$ Hi, sorry, could you clarify what you meant by casual configuration? Would my configuration be something like (12,1,7),(11,3,6),(10,2,8),(9,4,...? But then I'd start to repeat numbers. How would I build my sets of triples if this is what I have to do to solve the question? $\endgroup$ – Questioneer Jan 3 '15 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.