Tù nhân của vua Dadon

18

Tuy nhiên, trong hai lớp, tầng này chứa hơn một nửa số liên kết, tức là nhiều hơn $2^{r-1}$ liên kết. Các liên kết này không giao nhau và do đó, các tầng $r-1$ còn lại phải thực hiện phân tách bó các liên kết này, điều này là không thể, vì cấp độ của bó này lớn hơn $2^{r-1}$. Kết quả mâu thuẫn hoàn thành chứng minh.

Vì việc phân tách theo tầng của một hoán vị tùy ý (như $K_p$, không phải là một bó) yêu cầu không ít các tầng hơn so với việc phân tách bó tối đa của nó, nên điều đó là đúng.

Định lý 2. Số tầng tối thiểu cần thiết để thực hiện hoán vị hai giai đoạn của tấm bia $n$ và moltsna $p$ không nhỏ hơn $\log_2 p$.

Chúng tôi đã thu được ước tính “đáy” cho số tầng tối thiểu. Sử dụng các phép tính tương tự, bạn có thể nhận được ước tính từ phía trên:

Định lý 3. Một hoán vị tùy ý của gốc $n$ thừa nhận $\log_2 n [-\text{kаскадную реализацию}]$.

Bài toán 4. Chứng minh Định lý 3.

Kết quả ước tính “trên” và “dưới” khác nhau rất ít đối với các hoán vị “dày”. Tuy nhiên, đối với các hoán vị có độ dày nhỏ thì sự khác biệt về trọng lượng bị hạn chế và cần có những ước tính chính xác hơn. Hai bài toán tiếp theo đưa ra một số tiến bộ trong vấn đề này, nhưng công thức chính xác về số lượng giai đoạn hai giai đoạn tối thiểu cần thiết để phân tách một hoán vị nhất định vẫn chưa được biết.

Bài toán 5. Chứng minh rằng hoán vị độ dày $p$ thừa nhận việc thực hiện xếp tầng $(2 \cdot \log_2 p [-1])$.

Bài toán 6. Chứng minh rằng hoán vị độ dày $p$ cho phép thực hiện $(2 \cdot \log_2 \frac{p}{3} [+2])$-tầng.

Tù nhân của vua Dadon

Trong cuộc đột kích, vua Dadon đã bắt được 100 tù nhân. Họ bị biệt giam và lính canh được trang bị vũ khí dày đặc đi dọc hành lang nhà tù. Mỗi ô đều bị khóa; Tất cả một trăm ổ khóa đều có một chiếc chìa khóa được vua Dadon cất giữ trong rương. Một lượt chìa khóa mở được ổ khóa, một lượt khác lại khóa lại, lượt tiếp theo lại mở khóa lại, v.v.

Vào ngày sinh của ông, nhà vua quyết định thả tù nhân, thậm chí ngay trước ngày ông đã sai một người tra chìa khóa vào ổ khóa của buồng thác và xoay một vòng. Tất cả các cửa đều không khóa. Tuy nhiên, ngày sinh nhật vẫn chưa đến và không thể rời khỏi phòng giam: những người bảo vệ có vũ trang đi dọc hành lang.

Người đưa tin gần như không thể trả lại chìa khóa khi Vua Dadon thay đổi lời giải của mình. Ông ra lệnh cho người đưa tin mới vặn chìa khóa vào ổ khóa thác của căn phòng thứ hai. Cửa phòng giam thứ hai, thứ tư, thứ sáu và cả bốn phòng giam còn lại đều bị khóa lại. Người tiếp theo thực hiện một vòng quay trong ổ khóa của các phòng thứ ba, thứ sáu, thứ chín, thứ mười hai, v.v. Một cái khác nằm ở mỗi ô thứ tư. Điều tương tự cũng được lặp lại với thông điệp tiếp theo từ nhà vua - cho đến cả trăm, người chỉ vặn chìa khóa trong ổ khóa của căn phòng thứ trăm.

Cuối cùng, ngày sinh nhật của nhà vua đã được nhấn mạnh. Lính canh đã bị loại bỏ và những người trong phòng giam mở được thả ra.

Vua Dadon đã thả tự do cho bao nhiêu tù nhân?