Among 101 dalmatian dogs, each dog has a unique number of black spots from the set {1, 2, 3, . . . , 101}. We choose any 52 of the 101 dogs. We want to prove that any set of 52 dogs satisfies the following addition property:
Addition property: The numbers of spots on two of the dogs add up to exactly the number of spots on some other dog.
(a) Which proof technique is most appropriate and why?
(b) Prove that any set of 52 dogs has the addition property. Hint: First, prove the statement assuming that one of the 52 chosen dogs has 101 spots. Then generalize.
(c) How many among the 101 dogs have an odd number of spots that is not divisible by 3 and not divisible by 5. Show your work.
What I did
a) I am thinking it is the pigeonhole principle; however, I am confused on the potential setup.
b) 52+49 = 101 so this is two of the chosen dogs to 101. This can be generalized in that the second number can be decreased to get to 52+1= 53, this is the set of all dogs {53,54,..,101}, then 52 decreased in the same manner to 1+1=2 to get {2,3,...,52}, and some form of this to find the set of all dogs. However, I don't know how to formalize this proof nor what proof type it is.
c) This is inclusion-exclusion principle. I started off with 51 dogs, which have an odd number of spots, and proceeded to find A and B where A = Divisible by 3 and B = Divisible by 5, used the formula |A+B| = |A| + |B| - |A ∩ B|. To get 24 that are divisible by 3 and 5, subtract that from 51 to get 27 that aren't, so 27 is the final answer.
Question :
I am confused on what proof to use for B and how to set up A with pigeonhole principle.
I won't answer a, partly because it's based on an opinion, and partly because you have answered it.
Your answer for c is good, though for an alternate approach, consider the spots $\mathrm{mod} \ 30$ and note that only the following residues are favourable: $$1,7,11,13,17, 19, 23, 29$$ (specifically all the primes from 7 till 30 since any favourable composite must be at least $7 \times 7 = 49$)
Then, there are three groups of 30 (1-30, 31-60, 61-90) which give 24 numbers, and the last (incomplete) group from 91-101 gives 3, so we have $\boxed{27}$.
For the b part, let $k$ be the no. of spots of the dog with the highest no. of spots among the 52. Clearly, $101 \ge k \ge 52$. Then, all other 51 spots must be less than $k$. Consider the following pigeonholes: $$(1,k-1), (2,k-2), \ldots \left(\frac{k-1}{2}, \frac{k+1}{2}\right)\text{ or } \left(\frac{k}{2}-1, \frac{k}{2}+1\right)$$ where the last one depends on the parity of $k$. The elements in each pair sum to $k$. Your pigeons are the other $51$ numbers. Since $$\frac{k}{2}-1<\frac{k-1}{2} \le \frac{101-1}{2} = 50$$ at least one pigeonhole has 2 pigeons, i.e., out of the 51 other numbers, at least two belong to the same pair, which sum to $k$.