We call the permutation of subsets of set $ G_n$ described in problem a type 2 permutation. Lemma: There is a permutation of all (except empty set) subsets of the set $ G_n = \{1,2,...,n\}$: $ P_1,P_2,...,P_{2^n - 1}$ such that $ P_1 = \{1,2,...,n - 1\}$, $ P_{2^n - 1} = n$, $ P_{2^n - 2} \not = G_n$ and $ |P_i \cap P_{i + 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 $ G_n$ 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 $ G_n$ and let's prove it exists for $ G_{n + 1}$. By lemma there is type 1 permutation of $ G_n$. 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 $ G_{n + 1}$, call it $ Q$. By induction, there is type 2 permutation of $ G_n$ 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 $ G_{n + 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 $ G_{n + 1}$. Now, let's prove this lemma. This prove also goes by induction. Observe type 1 permutation of $ G_n$, $ P_1, P_2,..., P_{2^n - 1}$ where $ P_1 = \{1,2,...,n - 1\}$ and $ P_{2^n - 1} = \{n\}$ but $ P_{2^n - 2}\not = G_n$. Write it twice, but second time in inverse order $ P_1, P_2, P_3, ... , P_{2^n - 1}, P_{2^n - 1}, P_{2^n - 2}, ... ,P_1$. 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, ..., $ 2^{n + 1} - 2$th 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 $ G_{n + 1}$. What's more is that we get last subset to be $ \{n + 1\}$, the subset before him isn't $ G_{n + 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

SpongeBob wrote: By induction, there is type 2 permutation of $ G_n$ 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 $ G_{n + 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 $ G_{n + 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 $ G_{n + 1}$. why cant the set end with set $ \{n,n + 1\}$