Mèo Táo có mở một cửa hàng sách và đang cần tuyển nhân viên trông coi cửa hàng.

19/22

Mèo Táo có mở một cửa hàng sách và đang cần tuyển nhân viên trông coi cửa hàng. Để tuyển nhân viên đòi hỏi có khả năng tư duy và suy luận tốt, Táo đưa ra thử thách như sau: Bộ truyện tranh thám tử Kenichi gồm \(44\) tập đang được sắp xếp từ 1 tới \(44\) trên giá (giả sử đang tính từ trái qua phải và tất cả cuốn truyện được sắp xếp cùng chiều). Yêu cầu hãy thực hiện việc sắp xếp các tập truyện theo trình tự ngược lại từ \(44\) tới \(1\) theo quy tắc: Đổi chỗ \(2\) tập truyện đang xếp liên tiếp sẽ bị tính \(1\) điểm; đổi chỗ \(2\) tập truyện mà ở giữa chúng có \(3\) tập khác thì không bị tính điểm. Bạn An muốn ứng tuyển vào nhân viên cửa hàng. Hỏi điểm số nhỏ nhất của An là bao nhiêu điểm để thực hiện được thử thách trên?

Giải thích

Đáp án: \[22\]

Dãy số ban đầu là \[1;\;2;3;4;\;5;\;6;7;8;\;9;\;10;11;12;\;13;14;15;16;\; \ldots {\rm{ }};\;41;42;43;44\;\;\]

Gọi “lớp k” gồm các số của các tập truyện khi chia cho \[4\] dư \[k,\,\,1 \le k \le 4,\,k \in \mathbb{N}\]. Khi đó các số trong cùng một lớp có thể hoán đổi vị trí cho nhau mà không bị tính điểm.

Lớp 1: Các tập truyện mang số \[1;\;\;5;\;\;9;\;\;\;13;\; \ldots {\rm{ }};\;41\;\;\;\]

Lớp 2: Các tập truyện mang số \[2;\;\;6;\;\;10;\;14;\; \ldots {\rm{ }};\;42\]

Lớp 3: Các tập truyện mang số \[\;3;\;\;7;\;11;\;15;{\rm{ }} \ldots \;;\;43\;\]

Lớp 4: Các tập truyện mang số \[4;\;\;8;\;12;\;16; \ldots ;{\rm{ 44}}\]

Theo yêu cầu của Mèo Táo, cần sắp xếp các tập truyện theo thứ tự mới là:\[44;43;42;41;40;39;38;37;36;35;34;33;32;31;30;29;28;\,\,...\,\,;4;3;2;1\].

Nhận xét:

Các số ở lớp \[4\]cần đổi sang lớp 1 và ngược lại, các số ở lớp 2 đổi sang lớp \[3\] và ngược lại (Xem bảng minh họa)

Mèo Táo có mở một cửa hàng sách và đang cần tuyển nhân viên trông coi cửa hàng. (ảnh 1)

Do đó thực hiện hoán đổi cặp số L2 và L3 liền kề (\[11\] cặp), L4 và L\[1\] liền kề (\[10\] cặp), chỉ còn số \[1\] và \[44\] chưa được đổi lớp (Bị tính 21 điểm) (Xem bảng minh họa)

Mèo Táo có mở một cửa hàng sách và đang cần tuyển nhân viên trông coi cửa hàng. (ảnh 2)

Tiếp theo dùng quy tắc hoán đổi trong cùng một lớp sao cho số \[1\] và \[44\] lần lượt được xếp vào vị trí L\[1\] và L4 kế nhau rồi thực hiện hoán đổi hai tập truyện liền kề để đổi lớp (bị tính \[1\] điểm).

Cuối cùng dùng quy tắc hoán đổi không bị tính điểm các số trong từng lớp để được thứ tự theo yêu cầu.

Với cách thực hiện này An bị tính \[22\] điểm.

Vì mỗi số phải đổi lớp ít nhất một lần, với \[44\] số thì \[22\]lần hoán đổi hai vị trị liền kề là tối ưu nhất.

Vậy điểm số nhỏ nhất là \[22\]để An thực hiện được thử thách trên.