Mathematics Asked by TRONIIX on December 2, 2020
An inventory consists of an ordered list of $k$ items that are marked as "available" and $5$ items that are marked as "unavailable". What is the smallest value of $k$ such that we are certain that at least two items that are marked as available will be exactly three items apart in this list? Justify your answer. (Three apart means $A_i**A_j$ where each $*$ could be either $A$ or $U$).
I know this has to do with permutations and combinations but I’ve always been bad at them. I thought that the question would dumb down to identifying the extreme case and adding "$A$s" till the condition above has been satisfied but that seems quite wrong.
The trick is to look at every third item on the list. This splits the list into three sets: those at locations $1,4,7,10,...$, those at $2,5,8,11,...$, and those at $3,6,9,12,...$.
If you have only 5 unavailable items, one of these sets must have at most one unavailable item in it, by the pigeonhole principle. What does that mean for the size of that set if there are no two available items three-apart? What does that mean for the size of the other sets? And for the size of the list?
Once you have worked through those questions, you should be able to find an example of a longest possible list without a pair of three-apart available items, and then formulate a proof of why a list that is one item longer must contain such a pair.
Answered by Jaap Scherphuis on December 2, 2020
$k = 4$.
At $3$, $aaauuuuu$ is a counter-example.
Answered by William Elliot on December 2, 2020
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP