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.
Best Answer
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....