Chân ma

Ghost Leg (Chinese: 畫 鬼 腳), đượ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 Gost Leg được xử lý như một chuỗi, và sau khi Gost Leg đượ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.

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.

Hoán vị

Gosht leg 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 Gosht leg., [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 Gosh leg 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ỳ Gosht leg với ma trận đại diện M, tồn tại một Gosht leg 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 Gosht leg. 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 Gosht leg, 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 Gosht leg 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 Ghost Leg có thể được xây dựng tùy tiện, nhưng Ghost Leg không nhất thiết phải hoàn hảo. Có thể chứng minh rằng chỉ có những Ghost Legs được xây dựng hoàn hảo bằng cách sắp xếp ít chân nhất, do đó Gosht Legs 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 Gosht leg độ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.