Ghost Leg (), được biết đến ở Nhật như Amidakuji (, "xổ số Amida", nó được đặt tên như vậy bởi vì giấy được xếp thành hình quạt giống như vầng sáng của Amida hoặc ở Hàn Quốc được gọi là Sadaritagi (사다리 타기, nghĩa đen là "leo thang"),. Đây là một phương thức của thiết kế xổ số để tạo các cặp ngẫu nhiên giữa hai tập hợp của bất kỳ con số nào, miễn là số lượng các phần tử trong mỗi tập là như nhau. Điều này thường được sử dụng để phân phối những vật dụng chơi trong số những người, nơi mà số lượng những vật được phân phối bằng với số lượng người. Ví dụ, các công việc vặt hoặc phát giải thưởng có thể được thực hiện một cách công bằng và ngẫu nhiên theo cách này.

Nó bao gồm các đường thẳng đứng với các đường ngang kết nối hai đường thẳng liền kề nằm rải rác ngẫu nhiên dọc theo chiều dài của chúng; các đường ngang được gọi là "chân". Số cột thẳng đứng bằng số người đang chơi, và ở cuối mỗi cột có một mục - một vật sẽ được ghép nối với một người chơi. Quy tắc chung để chơi trò chơi này là: chọn một đường trên đầu trang, và đi từ trên xuống dưới. Khi gặp phải một đường ngang, người chơi phải theo đường ngang đó để tới một đường thẳng đứng khác và tiếp tục đi xuống. Lặp lại quy trình này cho đến khi kết thúc hàng dọc. Sau đó người chơi sẽ nhận được một vật được viết ở cuối dòng.

Nếu các yếu tố được viết trên chân ma được xử lý như một chuỗi, và sau khi chân ma được sử dụng, các yếu tố tương tự được viết ở phía dưới cùng, sau đó thứ tự bắt đầu sẽ được hoán đổi thành một trật tự khác. Do đó, Gosh Leg có thể được coi như là một hoán đổi của người chơi.

Quá trình chơi

Ví dụ: hãy xem xét giao vai trò trong vở kịch cho những diễn viên.

Để bắt đầu, hai bộ được liệt kê theo chiều ngang trên bảng. Tên của các diễn viên sẽ đặt ở trên cùng, và vai trò ở phía dưới cùng của ô. Sau đó, các đường thẳng đứng được vẽ kết nối mỗi diễn viên với vai diễn trực tiếp bên dưới.

Tên của các diễn viên và/hoặc vai trò được giấu kín để mọi người không biết diễn viên nào sẽ nhận được vai nào, hoặc vai diễn nào là trên đường dọc nào.

Tiếp theo, mỗi diễn viên thêm một chân vào bảng. Mỗi chân phải nối hai đường thẳng đứng liền kề, và không được chạm vào bất kỳ đường ngang nào khác.

Một khi điều này được thực hiện, một đường dẫn được bắt nguồn từ đầu của mỗi đường thẳng đứng đến đáy. Khi bạn đi theo đường từ trên xuống, nếu bạn đi qua một chân (hàng ngang), bạn phải rẽ theo nó tới đường thẳng đứng liền kề (liền kề bên trái hoặc bên phải), sau đó tiếp tục truy tìm đường đi. Bạn tiếp tục cho đến khi bạn đến chạm đến đường dưới cùng của một đường thẳng đứng, và tên trên hàng đầu bạn bắt đầu đã được ghép nối với vai diễn dưới cùng, sau đó trò chơi kết thúc. Quá trình chơi bao gồm việc tạo ra các bậc thang trước, sau đó giấu kín nó. Sau đó, mọi người lần lượt chọn một đường kẻ dọc bắt đầu từ phía trên cùng. Nếu không có phần nào của amidakuji được giấu, thì có thể sửa chữa hệ thống để bạn được đảm bảo có được một cặp nhất định, do đó đánh bại ý tưởng về cơ hội ngẫu nhiên.

Toán học

Một phần yêu cầu của cho trò chơi này, không giống như các trò chơi cơ hội ngẫu nhiên như đá, giấy, kéo, amidakuji luôn luôn tạo ra một sự tương ứng 1: 1, và có thể xử lý số lượng tùy ý của cặp (mặc dù bộ ghép nối với chỉ có hai mục từng cho rằng sẽ bị nhàm chán). Nó được đảm bảo rằng hai người chơi sẽ không bao giờ nhận cùng một mục tương ứng ở phía dưới, và cũng không bao giờ có bất kỳ mục nào ở dưới cùng bị thiếu một mục tương ứng ở đầu trang.

Trò chơi vẫn tiếp tục cho dù bất kể có bao nhiêu đường ngang được thêm vào. Mỗi người có thể thêm một, hai, ba, hoặc bất kỳ số hàng nào, và sự tương ứng 1: 1 sẽ vẫn còn.

Một cách để hiểu rõ cách thức chơi trò chơi này này là xem xét sự tương đồng của tiền xu trong cốc. Bạn có n đồng xu trong n cốc, đại diện cho các mặt hàng ở hàng dưới cùng của amidakuji. Sau đó, mỗi chân được thêm vào đại diện cho trao đổi vị trí của hai cốc liền kề. Vì vậy, rõ ràng là cuối cùng sẽ vẫn có n cốc, và mỗi cốc sẽ có một đồng xu, bất kể bạn thực hiện bao nhiêu hoán đổi.

Thuộc tính

Hoán vị

Chân ma biến đổi một dãy đầu vào thành một dãy đầu ra với cùng một số phần tử (có thể) với trật tự khác nhau. Như vậy, nó có thể được coi là một hoán vị của ký hiệu n, trong đó n là số các đường thẳng đứng trong chân ma., [2] do đó nó có thể được đại diện bởi ma trận hoán vị tương ứng.

Tính tuần hoàn

Áp dụng một chân ma một số lần hữu hạn cho một chuỗi đầu vào cuối cùng tạo ra một chuỗi đầu ra giống hệt với chuỗi nhập ban đầu. Tức là nếu M là một ma trận đại diện cho một chân Ghost cụ thể, sau đó Mn = I cho một số hữu hạn n.

Tính thuận nghịch

Đối với bất kỳ chân ma với ma trận đại diện M, tồn tại một chân ma với đại diện M-1, như M M-1=I

Hoán vị lẻ hoặc hoán vị ngang bằng

Khi mỗi chân trao đổi hai yếu tố cạnh nhau ở đầu, số chân cho biết thuộc tính lẻ / thậm chí là chuyển đổi của chân ma. Một số lẻ của chân đại diện cho một hoán vị lẻ, và sự ngang bằng về số chân sẽ cho sự ngang bằng về hoán vị.

Số chân vô hạn với cùng hoán vị

Có thể diễn tả mọi hoán vị như một chân ma, nhưng không thể hiện tỷ lệ 1-1, nghĩa là một hoán vị cụ thể không tương ứng với một chân ma duy nhất. Một số lượng vô hạn của Ghost Legs đại diện cho cùng một hoán vị.

Bóng ngắn và cách đơn giản nhất

Một chân ma có thể được xây dựng tùy tiện, nhưng chân ma không nhất thiết phải hoàn hảo. Có thể chứng minh rằng chỉ có những chân ma được xây dựng hoàn hảo bằng cách sắp xếp ít chân nhất, do đó chân ma rất ngắn. Điều này tương đương với việc cho rằng sắp xếp bong ngắn thực hiện số lượng tối thiểu các trao đổi liền kề đến một chuỗi ngắn.

Số chân tối đa của cách chơi hoàn hảo

Đối với một hoán vị với n phần tử, số lượng trao đổi liền kề tối đa = n(n-1)/2

Trong cùng một cách, số chân tối đa trong một cách hoàn hảo với n đường đi = n(n-1)/2

Bóng

Đối với một chân ma độc quyền, nó có thể thay đổi thành hoàn hảo bằng một cách gọi là bubblization. Khi bóng hoạt động, hai phần giống hệt nhau sau đây được áp dụng nhiều lần để di chuyển và loại bỏ chân "vô ích". Khi hai phần giống hệt nhau không thể được áp dụng nữa, Ghost Leg được chứng minh chính xác là giống như Ghost Leg được xây dựng bằng cách sắp xếp bóng, do đó bubblization có thể làm giảm Ghost Legs thành số nguyên tố.

Ngẫu nhiên

Như đã đề cập ở trên, một số lẻ các chân tạo ra một hoán chuyển lẻ và ngay cả khi một số đôi chân tạo ra sự hoán vị, số chân nhất định có thể tạo ra tối đa một nửa tổng số hoán vị (ít hơn một nửa nếu số chân là nhỏ so với số lượng đường đi, đạt một nửa số lượng chân tăng vượt quá một số tới hạn).

Nếu chân được vẽ ngẫu nhiên (đối với các định nghĩa của "rút ngẫu nhiên"), sự cân bằng của sự phân bố hoán vị tăng với số chân. Nếu số chân tương đối nhỏ so với số lượng đường đi, xác suất của hoán vị có thể đạt được khác nhau có thể khác nhau rất nhiều; trường hợp một số lượng lớn các chân xác suất của các hoán vị có thể đạt được khác nhau gần như bằng nhau.