1) Посмотрим, как выглядят плохие расстановки. Тогда ответ = количество хороших расстановок / количество всех расстановок. Обозначим расстановки карт как x = x_1 x_2 ... x_2n.
2) Количество всех расстановок (2n)!
3) Как выглядят плохие расстановки, те когда пасьянс в конце будет содержать >=3 карт?
Чтобы нельзя было сделать ход, нужно чтобы суффикс имел вид (1) ai * bj либо (2) bi * aj, где i != j, а * - любая карта. Заметим, что если какой-то суффикс x после всех просеиваний переходит в один из таких видов, то пасьянс не сойдётся. Можно доказать обратное: если никакой суффикс x при просеиваниях не перейдёт в (1) или (2), то пасьянс сойдется.
4) Из 3) можно построить все плохие расстановки. Они будут иметь вид:
x_1 ... x_[2n-3] bj x_[2n-1] ai
x_1 ... x_[2n-4] bj a_l1 a_l2 ai
x_1 ... x_[2n-5] bj a_l1 a_l2 a_l3 ai
x_1 ... x_[2n-5] bj a_l1 a_l2 a_l3 a_l4 ai
...
Здесь bj, ai, a_l1, a_l2, ... - выбранные карты (j != i), x_k - оставшиеся карты.
Аналогично к плохим расстановкам будут относится все с заменой местами bj и ai (вместо a_l1, a_l2, ... будут b_l1, b_l2, ...).
Первых расстановок ровно 2n*(n-1)*(2n-2)!
Вторых расстановок  2n*(n-1)*(n-1)*(n-2)*(2n-4)! = 2n*(n-1)*(n-1)! * (2n-4)!
Третьих расстановок  2n*(n-1)*(n-1)*(n-2)*(n-3)*(2n-5)! = 2n*(n-1)*(n-1)! / 2! * (2n-5)!
Четвертых расстановок  2n*(n-1)*(n-1)*(n-2)*(n-3)*(n-4)*(2n-6)! = 2n*(n-1)*(n-1)! / 3! * (2n-6)!
И т.д. до n+1.

Итого плохих расстановок bad_cnt = 2n*(n-1)*(2n-2)! + 2n*(n-1)*(n-1)! * sum((2n-k)!/(n-k+1)!), k=4,...,n+1

good_cnt = (2n)! - bad_cnt
d = gcd(good_cnt, (2n)!)
Ответ = (good_cnt / d, (2n)! / d)

PS: надеюсь не опечатался


Тесты:
(2, '2/3')
(3, '8/15')
(4, '13/28')
(5, '19/45')
(6, '13/33')
(7, '34/91')
(8, '43/120')
(9, '53/153')
(10, '32/95')
(11, '76/231')
(12, '89/276')
(13, '103/325')
(14, '59/189')
(15, '134/435')
(16, '151/496')
(17, '169/561')
(18, '94/315')
(19, '208/703')
(69, '2483/9453')
(100, '5149/19900')
(666, '111388/443223')
(1234, '381614/1522139')
(10000, '50014999/199990000')
(100000, '5000149999/19999900000')

Edited by author 12.08.2025 22:29