Prove that for arbitary positive integer n≥4, there exists a permutation of the subsets that contain at least two elements of the set Gn={1,2,3,⋯,n}: P1,P2,⋯,P2n−n−1 such that |Pi∩Pi+1|=2,i=1,2,⋯,2n−n−2.
Problem
Source:
Tags: induction, combinatorics proposed, combinatorics
05.04.2008 01:50
We call the permutation of subsets of set Gn described in problem a type 2 permutation. Lemma: There is a permutation of all (except empty set) subsets of the set Gn={1,2,...,n}: P1,P2,...,P2n−1 such that P1={1,2,...,n−1}, P2n−1=n, P2n−2≠Gn and |Pi∩Pi+1|=1. - type 1 permutation If we prove this lemma, then by induction, we can solve the problem: We prove by induction that there is type 2 permutation of Gn but with extra conditions, that starts and ends with two-element subsets, and the last subset doesn't contain n. Suppose that there exist such permutation for Gn and let's prove it exists for Gn+1. By lemma there is type 1 permutation of Gn. Add n+1 to every set in that permutation, then first subset is {1,2,...,n−1,n+1} and the last one is {n,n+1} and every two consecutive subsets have two elements in common now (the one they had before and n+1) - in this way we got some sequence of subsets of Gn+1, call it Q. By induction, there is type 2 permutation of Gn in which last element is two-element subset which doesn't contain n, and let this permutation be R. Those subsets in R and Q are in fact all subsets of Gn+1 that have at least two elements. Then just write permutation R and after it permutation Q. Last element in R is two-element subset which doesn't contain n, so it has two elements in common with first subset in Q which is {1,2,...,n−1,n+1}. But this permutation RQ ends with set {n,n+1} and we don't want that, so just look at permutation written in inverse order, and that's it, we got desirable permutation for Gn+1. Now, let's prove this lemma. This prove also goes by induction. Observe type 1 permutation of Gn, P1,P2,...,P2n−1 where P1={1,2,...,n−1} and P2n−1={n} but P2n−2≠Gn. Write it twice, but second time in inverse order P1,P2,P3,...,P2n−1,P2n−1,P2n−2,...,P1. In this sequnce again any two consecutive sets have one element in common. Now, start from the begginig and add n+1 to second, forth, sixth, ..., 2n+1−2th subset, and at the end write n+1. Observe that we didn't add n+1 to any consecutive subsets, but we got all subsets of Gn+1. What's more is that we get last subset to be {n+1}, the subset before him isn't Gn+1 (it's {1,2,...,n−1,n+1}) and everything we need is to get the first subset to be {1,2,...,n}. First subset in this sequence is {1,2,...,n−1}, and the subset {1,2,...,n} by induction wasn't adjecent with subset that contains n before adding n+1 to all subsets. So because we didn't add n+1 in first subset, we can just swich the first and one of the {1,2,...,n} in which we didn't add n+1, and that's it. My English is poor so just ask if you don't get something, or I made some mistakes Bye Example: n=3, type 1: 12,1,123,2,23,13,3, write it twice and add 4 to those on even places 12,1(4),123,2(4),23,13(4),3,3(4),13,23(4),2,123(4),1,12(4),(4), now swich 12 and 123. type 2 for n=4: 14,124,12,123,13,134,34,234,24,1234,23. For n=5 it's 14,124,12,123,13,134,34,234,24,1234,23 + 1235,1(4)5,125,2(4)5,235,13(4)5,35,3(4)5,135,23(4)5,25,123(4)5,15,12(4)5,(4)5 and just write it in inverse order
17.04.2008 06:01
SpongeBob wrote: By induction, there is type 2 permutation of Gn in which last element is two-element subset which doesn't contain n, and let this permutation be R. Those subsets in R and Q are in fact all subsets of Gn+1 that have at least two elements. Then just write permutation R and after it permutation Q. Last element in R is two-element subset which doesn't contain n, so it has two elements in common with first subset in Q which is {1,2,...,n−1,n+1}. But this permutation RQ ends with set {n,n+1} and we don't want that, so just look at permutation written in inverse order, and that's it, we got desirable permutation for Gn+1. ends with set {n,n+1} and we don't want that, so just look at permutation written in inverse order, and that's it, we got desirable permutation for Gn+1. why cant the set end with set {n,n+1}