- S and T have the same number of elements, - S and T are disjoint, and - the elements of S can be paired with the elements of T so that the elements in each pair differ by exactly 1.
For example, {1,2,5} and {0,3,4} are cousins. Suppose that the set S has exactly 4040 cousins. Find the least number of elements the set S can have.
On ∣S∣=n, find the number of cousins that S can have.
n=1 WLOG, S={1}.
{0} and {2} are cousins.
Therefore, S has 2 cousins.
n=2{1,2}⟶{0,3}⟶1 cousin{1,3}⟶{0,2},{0,4},{2,4}⟶3 cousins{1,4} Since ∣4−1∣=3, their adjacents are independent. 12×42=4 cases
n=4 Consider only sets in which all elements are related to each other, meaning the difference between consecutive elements of S is at most 2.
Other sets can be split into smaller independent sets and solved using the previous cases.
4040=23×5×101
By Hint 4, with 4 elements we can create 5 cousins.
⇒ By 100 elements we can create 101 cousins.
{1,3,5,7,…,199} has 101 cousins:
4040=23×5×101S={1,3,5,…,199,102,104,106,108,111,114,117}S1={1,3,5,…,199}⟶101 cousinsS2={102,104,106,108}⟶5 cousinsS3={111}⟶2 cousinsS4={114}⟶2 cousinsS5={117}⟶2 cousins S1,S2,S3,S4, and S5 are independent. ⇒S has 101×5×2×2×2=4040 cousinsAns≤∣S1∣+∣S2∣+∣S3∣+∣S4∣+∣S5∣=100+4+1+1+1=107 Now try to prove no one can find a better example than 107.
If we have n elements such that the difference of consecutive terms is at most 2 (can't be splitted into independent parts), then it has 0 or 1 or n+1 cousins. {1,3,5,…,2n−1}⟶ has n+1 cousins
Now we have 2 consecutive elements, then the pair of each element will be determined.Then if there is no conflict it would be 1 cousin, otherwise 0.
4040=23×5×101 By Hint 10, for creating 101 we need at least 100 related elements. If we want to, for example, combine 2,100, 2×100=200 we need at least 199 related elements, which is large.
Or if we combine 2,2, then 2×2=4 we need 3 related elements to create 4 cousins, but we can create 2 cousins with 1 element, so it's better to create cousins for each factor independently. ⇒Ans≤101100+54+21+21+21=107 By Hint 8, Ans=107
