But $45-32=13$ and the residue classes corresponding to $14,15,16$ can only have one representative - hence the maximum number of days is $2\times 13+3=29$ as you observe. Note that $28$ is possible because $14+28=42$ and the last residue class can have two representatives.įor $16$ the same applies - two residues only can be chosen from each class. That allows numbers to cover at most $28$ days. We therefore have at most two representatives of each residue class, and just $14$ classes. So we can't have $a_i\lt a_j \lt a_k$ in the same residue class as this would imply $a_k\gt 56$. I think your approach is quite neat, and can be made a bit more efficient as follows (it starts getting hard to make it an explicit pigeonhole approach, though that is in the background).įirst observe that if you take the $a_i$ as defined, and if the $14$-match criterion is not met, then if $a_i\equiv a_j \bmod 14$ we have that $a_i$ and $a_j$ must differ by at least $28$. What is the reason for the different answers? Is my approach flawed somehow? If so, how? Am I missing some assumption for the standard approach which doesn't apply to 16? Here's my question: Both of these can't be right. By the pigeonhole principle, it is impossible to choose 30 values from 1 to 45 without some 2 of those values having a difference of 16. If you use the approach I developed, you work out that you can choose a maximum of $(13)(\lceil 3/2 \rceil)+(3)(\lceil 2/2 \rceil)=29$ different integer values (such as 1 through 16 and 33 through 45) from 1 to 45 without having any 2 differ by exactly 16. This suggests that we can't apply the pigeonhole principle to this problem. If you use the standard approach, you still get 60 values as the pigeons, but a range of possible values from 1 to 61 as the number of pigeonholes. What happens if we keep the original question, but change it to ask about, say, consecutive days where the team must play 16 games. I've also found an important difference in these 2 approaches. I prefer this approach, as it doesn't add extra sets or values outside the original range, and in the process, you learn exactly the maximum amount of values you can choose in a range without having a specific difference. Since we're choosing 30 values, there must be at least 1 pair of values that differ by exactly 14. We now know that we can choose a maximum of 28 different values from this range in such a way that any 2 value do not differ by exactly 14. Also note that choosing just 1 more value means you must choose a number that differs from an already-chosen number by 14. For example, choosing the numbers 1 through 14, avoiding the numbers 15 through 28, and then choosing the numbers 29 through 42 gives you 28 numbers, none of which differ by exactly 14. Therefore, from the set of integers from 1 to 45, we can choose at most $(3)(2)+(11)(2)=28$ elements where no 2 differ by exactly 14. From the order 3 sets,you can choose a maximum of $\lceil 2/2 \rceil=2$ elements without having any 2 differ by exactly 14. From the order 4 sets, you can choose a maximum of $\lceil 4/2 \rceil=2$ elements without having any 2 differ by exactly 14. The standard solution involves defining the total number of games played by the end of day $i$ (where $i$ ranges from 1 to 30) as $a_$ are sets of order 3. Some number of consecutive days during which the team must play This starts with a classic pigeonhole principle question, which has appeared on Mathematics Stack Exchange before, in various forms:ĭuring a month with 30 days, a baseball team plays at least one game aĭay, but no more than 45 games.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |