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\}$