Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: Tìm tham số làm vô nghiệm hệ phương trình nguyên bậc 1

  1. #1
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Mặc định Tìm tham số làm vô nghiệm hệ phương trình nguyên bậc 1

    Bài toán này mình cần giải để dùng trong thiết kế. Nhưng bí quá. Ai có cao kiến gì không chỉ cho mình với.

    Đề bài. Có 3 biến số nguyên x[0], x[1], x[2] và 5 biến số nguyên y[0], y[1], y[2], y[3], y[4]. Với mọi k thuộc khoảng [0,32), giữa x[k] và y[k], trong đó chỉ số k được lấy mod 3 ở x và mod 5 ở y, có quan hệ y[k] = x[k] + c[k] (mod 32), với c[k] là tham số nhận giá trị từ [0,32) và các c[k] đôi một khác nhau. Hãy tìm một (bộ) giá trị cho các c[k] làm vô nghiệm mọi hệ phương trình có nhiều hơn 7 phương trình chọn từ 32 phương trình nói trên.

    EDIT. Mình không biết bài này có lời giải hay không.
    Đã được chỉnh sửa lần cuối bởi Ada : 25-04-2021 lúc 05:53 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  2. #2
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    662

    Chỗ quan hệ giữa xk, yk, ck là dấu bằng đồng dư(3 gạch ngang) đúng không?
    Ps: làm sao bạn gõ dấu ngoặc vuông vậy?

  3. #3
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Đúng rồi, là phương trình đồng dư. Viết dấu ngoặc nào cũng được, nhưng phải có dấu ngoặc, vì chỉ số là một biểu thức chứ không đơn giản là một số.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  4. #4
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Mình tìm được 2 lời giải. Bằng cách "mò hiện đại", hay còn gọi là phương pháp quy hoạch động (dynamic programming).

    Code:
    (a) 2 6 5 1 0 3 4 7 15 12 11 8 13 14 9 10 22 21 17 16 19 20 23 31 28 27 24 29 30 25 26 18
    (b) 5 1 2 6 7 4 3 0 8 11 12 15 10 9 14 13 17 18 22 23 20 19 16 24 27 28 31 26 25 30 29 21
    Hai lời giải này dù được tìm ra một cách độc lập nhưng xem ra chúng không "độc lập" với nhau mà có quan hệ rất chặt chẽ. Xem kỹ chúng có thể tìm ra thêm một số lời giải khác. Nhưng tuyệt nhiên đó không phải là tất cả những lời giải. Chắc là còn rất nhiều lời giải khác mà cách của mình không thể tìm ra được.

    Lúc nào rảnh rỗi mình sẽ gửi code của phần checker (tức là phần kiểm chứng rằng mọi hệ phương trình có nhiều hơn 7 phương trình đều vô nghiệm). Phần này đơn giản nhưng trong mấy năm qua mình đã tìm ra không biết bao nhiêu bug. Số bug chắc chắn nhiều hơn số ngón tay của 1 bàn tay. Và cứ mỗi lần như thế là sụp đổ cả 1 họ công thức, bao nhiêu công sức của cả đội đều đổ xuống... cống hết. Đến hôm nay, mình cũng chỉ dám chắc chắn 99% thôi.

    Ai có thời gian và công cụ vui lòng check 2 lời giải trên giúp mình với.

    Cảm ơn.
    Đã được chỉnh sửa lần cuối bởi Ada : 03-05-2021 lúc 10:36 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  5. #5
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Xin nói qua cách kiểm chứng.

    Các tham số c[k], đôi khi để cho tiện, còn được biểu diễn dưới dạng 2 chỉ số c[i,j] với i = k mod 3 và j = k mod 5. Tất nhiên, sự biểu diễn này là nhập nhằng (không đơn định) bởi vì một cặp (i,j) có thể chỉ ra nhiều giá trị k khác nhau. Chẳng hạn, c[0,0] có thể là c[0] nhưng cũng có thể là c[15] hay c[30].

    Phép tính k -> (i,j) như thế là hiển nhiên nhưng phép tính ngược lại, (i,j) -> k (chẳng hạn, thỏa giới hạn 0 <= k < 15) thì không hiển nhiên như thế. Tiểu thuyết Anh hùng xạ điêu nổi tiếng của Kim Dung có đoạn Hoàng Dung, Quách Tĩnh đến cầu kiến Anh Cô, một nhân vật nổi tiếng vì "thần cơ diệu toán", nhưng khó tính, không ưa giao tiếp. Để làm khó 2 người khách, bà chủ nhà đưa ra bài toán (mà chính bà không giải được) như thế này. Có k quả táo, chia cho 3 người thì dư i quả, chia cho 5 người thì dư j quả, hỏi k là bao nhiêu. Vị khách nữ đã vượt qua thử thách này.

    Tìm một công thức để tính (i,j) -> k là một bài tập tốt để vào đề cho bài toán chính. Trong khi chưa có công thức như thế, cách tính dễ nhất là... không tính gì cả. Nghĩa là lập bảng tra và học thuộc lòng, giống như bảng cửu chương.

    Code:
      |  0 |  1 |  2 |  3 |  4 |
    --+----+----+----+----+----+
    0 |  0 |  6 | 12 |  3 |  9 |
    --+----+----+----+----+----+
    1 | 10 |  1 |  7 | 13 |  4 |
    --+----+----+----+----+----+
    2 |  5 | 11 |  2 |  8 | 14 |
    --+----+----+----+----+----+
    Nói về hệ phương trình chủ đề, mình thường dùng ngôn ngữ của lý thuyết đồ thị. Mình nhìn vào hệ phương trình y[k] = x[k] + c[k] (mod 32), hay nói cách khác, y[j] = x[i] + c[i,j], như một đồ thị (vô hướng, hai phía) mà mỗi đỉnh thể hiện 1 biến số (ẩn số) và mỗi cung thể hiện 1 phương trình. Phương trình liên hệ biến x[i] với biến y[j] tất nhiên tương ứng với cung nối 2 đỉnh tương ứng với x[i] và y[j].

    Trong cách nhìn ấy, sự khác biệt giữa một hệ có ít phương trình và một hệ có nhiều hơn 7 phương trình trở nên rõ rệt: đồ thị của một hệ có nhiều hơn 7 phương trình chắc chắn phải có ít nhất 1 chu trình (nghĩa là vòng tròn khép kín); đồ thị của một hệ có không quá 7 phương trình có thể, nhưng không nhất thiết phải có chu trình nào.

    Thí dụ, hai phương trình y[0] = x[0] + c[0] (mod 32) và y[0] = x[0] + c[15] (mod 32) ứng với một 2-chu trình (tức chu trình có 2 cung) từ đỉnh x[0] qua cung y[0] = x[0] + c[0] (mod 32), từ đây gọi tắt là cung c[0] hoặc cung 0, đến đỉnh y[0], rồi qua cung 15 trở về đỉnh x[0].

    Đi dọc theo chu trình này, ta rút ra x[0] + c[0] = x[0] + c[15] (mod 32), suy ra c[0] = c[15] (mod 32). Điều này không thể xảy ra khi các c[k] đều thuộc khoảng [0,32) và đôi một khác nhau. Nghĩa là mọi đồ thị chứa 2-chu trình này đều bất khả thi hay nói đơn giản hơn, bất cứ hệ phương trình nào chứa hai phương trình 0 và 15 đều vô nghiệm.

    Không phải là chu trình nào cũng đáng quan tâm. Thí dụ, 4-chu trình với các cung 5 = (2,0), 10 = (1,0), 25 = (1,0), 20 = (2,0) theo thứ tự đó, vốn chỉ có 3 đỉnh x[1], x[2] và y[0] và vốn được ghép từ hai 2-chu trình 5-20 và 10-25, không đem lại điều gì mới hơn hai chu trình sau, nên chẳng đáng quan tâm.

    Một chu trình là đáng quan tâm khi và chỉ khi nó có số đỉnh bằng số cung.

    Hình sau đây thế hiện một 4-chu trình đáng quan tâm. Các hệ thức đồng dư ràng buộc đảm bảo rằng 4 cung thực sự nối với nhau thành 1 chu trình và các hệ thức bất đồng dư ràng buộc đảm bảo rằng 4 đỉnh là phân biệt, nghĩa là chu trình không suy biến thành một hình dạng khác. Mọi 4-chu trình đáng quan tâm đều có hình dạng như thế.

    Code:
        x[k]       x[k']
         o           o
         |\         /|
         | \    k' / |
         |  \     /  |
         |   \   /   |
         |    \ /    |
       k |     /     | k'*
         |    / \    |
         |   /   \   |
         |  /     \  |
         | /    k* \ |
         |/         \|
         o           o
        y[k]       y[k*]
    
    k'  = k  (mod 5), k'  != k  (mod 3)
    k*  = k  (mod 3), k*  != k  (mod 5)
    k'* = k' (mod 3), k'* != k' (mod 5)
    k'* = k* (mod 5), k'* != k* (mod 3)
    Tương tự, một 6-chu trình đáng quan tâm có hình dạng như sau. Các hệ thức ràng buộc, xin nhường cho bạn đọc.

    Code:
        x[k]       x[k']       x[k'']
         o           o           o
         |\         / \         /|
         | \    k' /   \ k'**  / |
         |  \     /     \     /  |
         |   \   /       \   /   |
         |    \ /         \ /    |
       k |     /           /     | k''**
         |    / \         / \    |
         |   /   \       /   \   |
         |  /     \     /     \  |
         | /    k* \   / k''*  \ |
         |/         \ /         \|
         o           o           o
        y[k]       y[k*]       y[k**]
    Nếu xem xét một chu trình đáng quan tâm trong đồ thị (trong bài toán cụ thể này, đáng quan tâm chỉ có 3 loại là 2-, 4- và 6-chu trình nói trên) và bác bỏ được đồng dư thức liên quan, cụ thể, đồng dư thức dạng đơn giản như ở 2-chu trình trong thi dụ trên, với k = k' (mod 15),
    Code:
    c[k] = c[k'] (mod 32)
    hay đồng dư thức dạng phức tạp hơn, ở 4-chu trình trong hình vẽ thứ nhất,
    Code:
    c[k] + c[k*'] = c[k'] + c[k*] (mod 32)
    hay đồng dư thức dạng phức tạp nhất, ở 6-chu trình trong hình vẽ thứ hai,
    Code:
    c[k] + c[k''*] + c[k'**] = c[k'] + c[k''**] + c[k*] (mod 32)
    thì có thể khẳng định mọi hệ phương trình chứa 2, 4 hay 6 phương trình tương ứng là vô nghiệm và vì thế, duyệt hết mọi chu trình, bác bỏ hết mọi đồng dư thức liên quan thì đương nhiên khẳng định được mọi hệ phương trình có nhiều hơn 7 phương trình đều vô nghiệm.

    Mặt khác, dễ thấy rằng một hệ phương trình nếu có đồ thị hình cây (tree) thì chắc chắn có nghiệm. Thế nên đảo lại, chỉ cần 1 chu trình thoả mãn đồng dư thức liên quan là ta có ngay một hệ 8 phương trình có nghiệm. Thật vậy, chỉ cần chọn thêm vài cung sao cho các cung vừa chọn thêm cùng với chu trình vừa tìm thấy tạm bỏ đi (trong tưởng tượng) 1 cung bất kỳ hợp thành một cây khung (spanning tree) là xong.

    Vậy, mọi chu trình đáng quan tâm được duyệt và mọi đồng dư thức liên quan đều bị bác bỏ là điều kiện đủ và cũng là điều kiện cần để cho vô nghiệm mọi hệ nhiều hơn 7 phương trình.

    Để trả lời cho câu hỏi cách này có gì hay hơn cách "thông thường", như là lập và giải thử mọi hệ 8 phương trình, xin nêu 2 con số. Với 1 bộ tham số c[k] tiềm năng, có hơn 10 triệu cách chọn ra 8 phương trình từ 32 phương trình. Trong khi ấy, số chu trình đáng quan tâm là... đủ ít để trong vòng 1 tiếng đồng hồ, mình duyệt được hơn 10 triệu hoán vị của khoảng [0,32), tức 10 triệu bộ tham số c[k] tiềm năng, 10 triệu lần duyệt hết mọi chu trình đáng quan tâm, để tìm được 2 lời giải.

    Khỏi cần phải nói mình đã may mắn như thế nào: 10 triệu hoán vị của 32 số mới chỉ là một phần vô cùng nhỏ của tổng số 32! = 263130836933693530167218012160000000 hoán vị. Nếu phải duyệt hết số hoán vị to lớn này, kể cả với tốc độ "cực nhanh" nêu trên, mình cũng cần đến 26313083693369353016721801216 ~ 3E28 giờ. So với đó, số tuổi của Vũ Trụ, ~ 1E14 giờ, chỉ là một cái chớp mắt mà thôi.
    Đã được chỉnh sửa lần cuối bởi Ada : 27-05-2021 lúc 12:02 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  6. #6
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    662

    Mặc định Tìm tham số làm vô nghiệm hệ phương trình nguyên bậc 1

    Cách kí hiệu của bạn gây hiểu lầm
    Code:
       x[k mod 3]  x[k' mod 3]
       x[k* mod 3] x[k'* mod 3]
         o           o
         |\         /|
         | \    k' / |
         |  \     /  |
         |   \   /   |
         |    \ /    |
       k |     /     | k'*
         |    / \    |
         |   /   \   |
         |  /     \  |
         | /    k* \ |
         |/         \|
         o           o
        y[k mod 5]   y[k* mod 5]
        y[k' mod 5]  y[k'* mod 5]
    
    k'  = k  (mod 5), k'  != k  (mod 3}
    k*  = k  (mod 3), k*  != k  (mod 5)
    k'* = k' (mod 3), k'* != k' (mod 5)
    k'* = k* (mod 5), k'* != k* (mod 3)
    - - - Nội dung đã được cập nhật ngày 06-05-2021 lúc 09:15 PM - - -

    Còn về dấu ngoặc vuông ý mình là làm sao gõ được nó trong bài viết khi nó đã được dành riêng để sử dụng như thẻ định dạng in đậm in nghiêng url...

  7. #7
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Chỉ số của x và của y được lấy mod 3 và mod 5. Đó là quy ước ngay từ bài đầu. Đó cũng là quy ước thông dụng trong các bài viết, báo cáo, tài liệu,... có sử dụng mod ở chỉ số hay số mũ. Mục đích là để biểu thức của chỉ số hay số mũ đơn giản, dễ đọc.

    EDIT. Còn lý do thẩm mỹ nữa. Biểu thức chỉ số hay số mũ mà phức tạp thì in ra trông rất xấu. Đó là lý do trong khoa học, khi cần viết hàm số mũ với số mũ là một biểu thức phức tạp kiểu như F(...), người ta không viết là e^F(...), F(...) in cỡ nhỏ ở trên cao, mà viết là exp F(...), F(...) in cỡ thường và ngang hàng với exp.

    Dấu ngoặc vuông... Mình cứ viết bình thường thôi, không thấy báo lỗi gì.
    Đã được chỉnh sửa lần cuối bởi Ada : 07-05-2021 lúc 01:05 AM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  8. #8
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Một ứng dụng của chỉ số dạng cặp (k mod 3, k mod 5) thay cho k là giúp nhìn thấy tính chất của chu trình đáng quan tâm (xem 2 hình vẽ trên), suy trực tiếp từ điều kiện ràng buộc. Cụ thể, 4-chu trình có tính chất
    Code:
    k + k*'  =  k' + k*   (mod 15)
    và 6-chu trình có tính chất
    Code:
    k + k''* + k'**   =   k' + k''** + k*    (mod 15)
    Tính chất này xem ở dạng mod 15, ta thấy khả nghi, nhưng xem ở dạng (mod 3, mod 5) thì thấy hiển nhiên, đến mức không cần phải chứng minh.

    Chẳng hạn, chu trình 12-7-13-3, tức (0,2)(1,2)(1,3)(0,3):
    Code:
    12 + 13 = 7 + 3 (mod 15)
    (0,2) + (1,3) = (1,2) + (0,3) (mod 3, mod 5)
    và chu trình 12-7-13-8-14-9, tức (0,2)(1,2)(1,3)(2,3)(2,4)(0,4):
    Code:
    12 + 13 + 14 = 7 + 8 + 9 (mod 15)
    (0,2) + (1,3) + (2,4) = (1,2) + (2,3) + (0,4) (mod 3, mod 5)
    Ứng dụng khác là tính xem có bao nhiêu chu trình đáng quan tâm.

    Nếu chỉ có 15 phương trình thì dễ quá. Đối với 4-chu trình, chọn cung thứ nhất bất kỳ, cung thứ hai độc lập với cung thứ nhất, nghĩa là không có đỉnh nào chung với cung thứ nhất, nghĩa là chỉ số của chúng không đồng dư mod 3 mà cũng chẳng đồng dư mod 5. (Hai cung còn lại hoàn toàn xác định từ 2 cung vừa chọn.) Đối với 6-chu trình, thì chọn thêm cung thứ ba độc lập với hai cung đầu nữa. (Ba cung còn lại hoàn toàn xác định từ 3 cung vừa chọn.)

    Với mỗi cách chọn cung thứ nhất, có 8 cách chọn cung thứ hai và một khi hai cung ấy đã chọn, sẽ có 3 cách chọn cung thứ ba. Để tin được điều này mà không cần dùng đến định lý nào về số học, chỉ cần xem bảng tính (k mod 3, k mod 5) -> k đã nêu ở bài trước: cung thứ nhất là một ô bất kỳ trong bảng; cung thứ hai là một ô khác không cùng hàng mà cũng chẳng cùng cột với ô đầu, và cung thứ ba là một ô khác nữa, không cùng hàng mà cũng chẳng cùng cột với hai ô vừa kể. Nhân tiện, đối với 4-chu trình, hai cung (phụ thuộc) còn lại được xác định như sau: cung thứ ba là ô cùng côt với ô độc lập thứ nhất và cùng hàng với ô độc lập thứ hai, cung thứ tư là ô cùng cột với ô độc lập thứ hai và cùng hàng với ô độc lập thứ nhất; tóm lại, 4 cung là 4 ô ở đỉnh của một hình chữ nhật. Đối với 6-chu trình, cũng tương tự, và 6 ô là 6 đỉnh của một hình thước thợ (hình lục giác vuông góc).

    Đếm mọi cách chọn như thế, mỗi 4-chu trình được tính lặp 4 lần và mỗi 6-chu trình sẽ được tính lặp 6 lần. Nên số 4-chu trình là 15*8/4 = 30, số 6-chu trình là 15*8*3/6 = 60.

    Nếu có 30, 45,... phương trình thì cũng dễ quá. Mỗi cặp chỉ số (i,j) ứng với đúng 2, 3,... giá trị khả dĩ cho chỉ số k, mỗi 4-chu trình vừa kể tương ứng với 2^4, 3^4,... giá trị cho bộ tứ (k,k',k*,k'*), nghĩa là số 4-chu trình sẽ được nhân lên 2^4, 3^4,... lần. Tương tự, số 6-chu trình sẽ được nhân lên 2^6, 3^6,... lần.

    Nhưng ở đây số phương trình lại là 32, nên rắc rối.

    Vậy, rút cuộc, có bao nhiêu chu trình đáng quan tâm?

    Mình tiếc là đã không tự hỏi câu này sớm hơn. Để trả lời nó, mình chỉ tốn 1 giờ bên bảng đen phấn trắng. Nhưng để nghĩ ra nó, mình mất gần 10 năm. Phải, mình đã tiêu phí 10 năm vì chủ quan tin vào một chương trình máy tính, cho một con tính quan trọng như thế. Đến giờ, mình vẫn thỉnh thoảng giữa đêm choàng tỉnh dậy vì một cơn ác mộng: nó, cái chương trình chết tiệt ấy, lại tính sai.

    Mỗi cặp chỉ số (i,j) ứng với 2 hoặc 3 chỉ số k, theo bảng sau.

    Bảng 1. Số cung (số giá trị k) cho mỗi giá trị cặp chỉ số i, j (k mod 3, k mod 5).
    Code:
      | 0 | 1 | 2 | 3 | 4 |
    --+---+---+---+---+---+
    0 | 3 | 2 | 2 | 2 | 2 |
    --+---+---+---+---+---+
    1 | 2 | 3 | 2 | 2 | 2 |
    --+---+---+---+---+---+
    2 | 2 | 2 | 2 | 2 | 2 |
    --+---+---+---+---+---+
    Từ đó, ta phân biệt các trường hợp rồi tính số chu trình cho từng trường hợp. Gọi P(n,k) là số hoán vị k phần tử chọn từ n phần tử (còn gọi là chỉnh hợp khi k != n), các 4-chu trình có P(5,2) * P(3,2) = 120 trường hợp, các 6-chu trình có P(5,3) * P(3,3) = 360 trường hợp. Tuy số trường hợp nhiều, nhưng các trường hợp quy tụ thành nhóm tuỳ theo các ô được chọn có thuộc về cột 0, 1 và/hoặc hàng 0, 1 hay không. Mỗi nhóm như thế, chỉ cần tính vài trường hợp tiêu biểu là đủ. Kết quả được trình bày trong Bảng 2 và Bảng 3.

    Bảng 2. Tính số 4-chu trình. Tiêu đề cột là chỉ số của cặp cung độc lập lấy mod 3 (i, i'*) còn tiêu đề hàng là chỉ số tương ứng lấy mod 5 (j,j'*). Chẳng hạn, cột (0,1) hàng (2,3) thể hiện chu trình (0,2)(1,2)(1,3)(0,3).
    Code:
          0,1     1,0     0,2     2,0     1,2     2,1
    ===== ======= ======= ======= ======= ======= =======
    0,1   2^2*3^2 2^2*3^2 2^3*3   2^3*3   2^3*3   2^3*3  
    1,0   2^2*3^2 2^2*3^2 2^3*3   2^3*3   2^3*3   2^3*3  
    ----- ------- ------- ------- ------- ------- -------
    0,2   2^3*3   2^3*3   2^3*3   2^3*3   2^4     2^4    
    2,0   2^3*3   2^3*3   2^3*3   2^3*3   2^4     2^4    
    ... 12 hàng cả thảy. Thay 0 bằng 1, thay 2 bằng 3,4
         để được 10 hàng còn lại.
    ----- ------- ------- ------- ------- ------- -------
    2,3   2^4     2^4     2^4     2^4     2^4     2^4    
    3,2   2^4     2^4     2^4     2^4     2^4     2^4    
    ... 6 hàng cả thảy. Thay {2,3} bằng {2,4},{3,4} để
        thu được 4 hàng còn lại.
    ----- ------- ------- ------- ------- ------- -------

    Bảng 3. Tính số 6-chu trình. Tiêu đề cột là chỉ số của bộ 3 cung độc lập mod 3 còn tiêu đề hàng là chỉ số tương ứng mod 5. Chẳng hạn, cột (0,1,2) hàng (2,3,4) thể hiện chu trình (0,2)(1,2)(1,3)(2,3)(2,4)(0,4).
    Code:
          0,1,2   0,2,1   2,0,1   2,1,0   1,2,0   1,0,2
    ===== ======= ======= ======= ======= ======= =======
    0,1,2 2^4*3^2 2^4*3^2 2^4*3^2 2^5*3   2^6     2^5*3  
    0,2,1 2^5*3   2^4*3^2 2^4*3^2 2^6     2^5*3   2^4*3^2
    2,0,1 2^6     2^5*3   2^4*3^2 2^5*3   2^4*3^2 2^4*3^2
    2,1,0 2^4*3^2 2^5*3   2^5*3   2^4*3^2 2^4*3^2 2^6    
    1,2,0 2^4*3^2 2^5*3   2^6     2^4*3^2 2^4*3^2 2^5*3  
    1,0,2 2^5*3   2^6     2^5*3   2^4*3^2 2^4*3^2 2^4*3^2
    ... 18 hàng cả thảy. Thay 2 bằng 3,4 để thu được 
            12 hàng còn lại.
    ----- ------- ------- ------- ------- ------- -------
    0,2,3 2^5*3   2^5*3   2^5*3   2^6     2^6     2^5*3  
    0,3,2 2^5*3   2^5*3   2^5*3   2^6     2^6     2^5*3  
    3,0,2 2^6     2^6     2^5*3   2^5*3   2^5*3   2^5*3  
    3,2,0 2^5*3   2^5*3   2^6     2^5*3   2^5*3   2^6    
    2,3,0 2^5*3   2^5*3   2^6     2^5*3   2^5*3   2^6    
    2,0,3 2^6     2^6     2^5*3   2^5*3   2^5*3   2^5*3  
    ... 36 hàng cả thảy. Thay 0 bằng 1, thay {2,3}
        bằng {2,4},{3,4} để được 30 hàng còn lại.
    ----- ------- ------- ------- ------- ------- -------
    2,3,4 2^6     2^6     2^6     2^6     2^6     2^6    
    ... 6 hàng cả thảy, gồm mọi hoán vị của {2,3,4}
    ----- ------- ------- ------- ------- ------- -------
    Nhắc lại, mỗi 4-chu trình được tính lặp 4 lần. Chẳng hạn, bốn 4-chu trình sau đây thật ra là một.
    Code:
    Cột    Hàng   Thể hiện chu trình
    
    (0,1)  (2,3)  (0,2)(1,2)(1,3)(0,3)
    (0,1)  (3,2)  (0,3)(1,3)(1,2)(0,2)
    (1,0)  (2,3)  (1,2)(0,2)(0,3)(1,3)
    (1,0)  (3,2)  (1,3)(0,3)(0,2)(1,2)
    Tương tự, mỗi 6-chu trình được tính lặp 6 lần. Chẳng hạn, sáu 6-chu trình sau đây thật ra là một.
    Code:
    Cột      Hàng     Thể hiện chu trình
    
    (0,1,2)  (2,3,4)  (0,2)(1,2)(1,3)(2,3)(2,4)(0,4)
    (0,2,1)  (4,3,2)  (0,4)(2,4)(2,3)(1,3)(1,2)(0,2)
    (2,0,1)  (4,2,3)  (2,4)(0,4)(0,2)(1,2)(1,3)(2,3)
    (2,1,0)  (3,2,4)  (2,3)(1,3)(1,2)(0,2)(0,4)(2,4)
    (1,2,0)  (3,4,2)  (1,3)(2,3)(2,4)(0,4)(0,2)(1,2)
    (1,0,2)  (2,4,3)  (1,2)(0,2)(0,4)(2,4)(2,3)(1,3)
    Từ Bảng 2, tính được tổng số là
    Code:
         2 * (2 * 2^2*3^2 + 4 * 2^3*3)
      + 12 * (4 * 2^3*3 + 2 * 2^4)
      +  6 * 6 * 2^4
    = 2448.
    Do mỗi 4-chu trình được tính lặp 4 lần, số 4-chu trình thực sự (không trùng lặp) là 2448/4 = 612.

    Tương tự, từ Bảng 3, tính được tổng số là
    Code:
        18 * (3 * 2^4*3^2 + 2 * 2^5*3 + 2^6)
      + 36 * (4 * 2^5*3 + 2 * 2^6)
      +  6 * 6 * 2^6
    = 33120.
    Do mỗi 6-chu trình được tính lặp 6 lần, số 6-chu trình thực sự (không trùng lặp) là 33120/6 = 5520.
    Đã được chỉnh sửa lần cuối bởi Ada : 10-05-2021 lúc 01:53 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  9. #9
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Đây là code của phần kiểm chứng. Không phải là code mình vẫn dùng, là code mới. Mình viết nó để kiểm chứng kết quả một cách "độc lập" với code cũ của mình.

    Nó theo sát mô tả trong 2 bài trên. Nó in ra 2 bảng thống kê số chu trình đã duyệt theo định dạng giống như Bảng 2 và Bảng 3 trong bài trên, và kết luận (PASS là đạt, FAIL là trượt).

    Do giả định dữ liệu đầu vào đã là hoán vị, mình bỏ qua các 2-chu trình.

    Phần chính
    C++ Code:
    1. void alt_analyze( int c[32] )
    2. {
    3.     /// An analysis of the 32-sequence.
    4.     ///
    5.     /// Problem. Given 8 integer (unknown) variables x[0],x[1],x[2] and
    6.     /// y[0],y[1],y[2],y[3],y[4], consider 32 simultaneous linear congruential
    7.     /// equations
    8.     ///
    9.     ///    y[k] = x[k] + c[k]    (mod 32)
    10.     ///
    11.     /// where
    12.     ///
    13.     ///    k in [0,32), the subscript k in x[k], y[k] is taken mod 3, mod 5
    14.     ///    respectively;
    15.     ///
    16.     ///    c[k] in [0,32), c[k] are all different, i.e. the mapping k -> c[k]
    17.     ///    is a permutation of the range [0,32).
    18.     ///
    19.     /// Check if the set of parameters c[k] (which is supposedly a
    20.     /// permutation) makes every system of 8 or more equations chosen from
    21.     /// the 32 equations non-soluble.
    22.  
    23.     int const M = 32;
    24.  
    25.     int Sun_tzu[3][5];
    26.     for( int k=0; k<15; k++ ) { Sun_tzu[k%3][k%5] = k; }
    27.     int occurs[3][5] = {0};
    28.     for(int k=0; k < M; k++){ ++occurs[k%3][k%5]; }
    29.  
    30.     bool ok = true;
    31.  
    32.     // 4-cycle enumeration
    33.  
    34.     int const C_3_2 = 3;
    35.     int const C_5_2 = 10;
    36.     int const P_2_2 = 2;
    37.     int const P_3_2 = C_3_2 * P_2_2;
    38.     int const P_5_2 = C_5_2 * P_2_2;
    39.     std::vector<Tuple> L2i, L2j;
    40.  
    41.     list_permutation(L2i,3,2);
    42.     list_permutation(L2j,5,2);
    43.     int C2counter[P_5_2][P_3_2] = {0};
    44.     for( size_t ii = 0; ii < L2i.size(); ii++ ){
    45.         int i0 = L2i[ii][0];
    46.         int i2 = L2i[ii][1];
    47.         int i1 = i2;
    48.         int i3 = i0;
    49.  
    50.         for( size_t jj = 0; jj < L2j.size(); jj++ ){
    51.             int j0 = L2j[jj][0];
    52.             int j2 = L2j[jj][1];
    53.             int j1 = j0;
    54.             int j3 = j2;
    55.             for( int n0 = 0; n0 < occurs[i0][j0]; n0++ ) {
    56.                 int k0 = Sun_tzu[i0][j0] + 15*n0;
    57.                 for( int n1 = 0; n1 < occurs[i1][j1]; n1++ ){
    58.                     int k1 = Sun_tzu[i1][j1] + 15*n1;
    59.                     for( int n2 = 0; n2 < occurs[i2][j2]; n2++ ){
    60.                         int k2 = Sun_tzu[i2][j2] + 15*n2;
    61.                         for( int n3 = 0; n3 < occurs[i3][j3]; n3++ ){
    62.                             int k3 = Sun_tzu[i3][j3] + 15*n3;
    63.                             ok &= ( (c[k0] - c[k1] + c[k2] - c[k3]) % M != 0 );
    64.                             C2counter[jj][ii]++;
    65.                         }
    66.                     }
    67.                 }
    68.             }
    69.         }
    70.     }
    71.  
    72.     // 6-cycle enumeration
    73.  
    74.     int const C_5_3 = 10;
    75.     int const P_3_3 = 6;
    76.     int const P_5_3 = C_5_3 * P_3_3;
    77.     std::vector<Tuple> L3i, L3j;
    78.  
    79.     list_permutation(L3i,3,3);
    80.     list_permutation(L3j,5,3);
    81.     int C3counter[P_5_3][P_3_3] = {0};
    82.     for( size_t ii = 0; ii < L3i.size(); ii++ ){
    83.         int i0 = L3i[ii][0];
    84.         int i2 = L3i[ii][1];
    85.         int i4 = L3i[ii][2];
    86.         int i1 = i2;
    87.         int i3 = i4;
    88.         int i5 = i0;
    89.  
    90.         for( size_t jj = 0; jj < L3j.size(); jj++ ){
    91.             int j0 = L3j[jj][0];
    92.             int j2 = L3j[jj][1];
    93.             int j4 = L3j[jj][2];
    94.             int j1 = j0;
    95.             int j3 = j2;
    96.             int j5 = j4;
    97.             for( int n0 = 0; n0 < occurs[i0][j0]; n0++ ) {
    98.                 int k0 = Sun_tzu[i0][j0] + 15*n0;
    99.                 for( int n1 = 0; n1 < occurs[i1][j1]; n1++ ){
    100.                     int k1 = Sun_tzu[i1][j1] + 15*n1;
    101.                     for( int n2 = 0; n2 < occurs[i2][j2]; n2++ ){
    102.                         int k2 = Sun_tzu[i2][j2] + 15*n2;
    103.                         for( int n3 = 0; n3 < occurs[i3][j3]; n3++ ){
    104.                             int k3 = Sun_tzu[i3][j3] + 15*n3;
    105.                             for( int n4 = 0; n4 < occurs[i4][j4]; n4++){
    106.                                 int k4 = Sun_tzu[i4][j4] + 15*n4;
    107.                                 for( int n5 = 0; n5 < occurs[i5][j5]; n5++){
    108.                                     int k5 = Sun_tzu[i5][j5] + 15*n5;
    109.                                     ok &= ((c[k0]-c[k1]+c[k2]-c[k3]+c[k4]-c[k5]) % M != 0);
    110.                                     C3counter[jj][ii]++;
    111.                                 }
    112.                             }
    113.                         }
    114.                     }
    115.                 }
    116.             }
    117.         }
    118.     }
    119.  
    120.     print_table(C2counter, L2j, L2i);
    121.     print_table(C3counter, L3j, L3i);
    122.  
    123.     printf("Verdict: %s\n", ok ? "PASS":"FAIL");
    124. }

    Phần phụ
    C++ Code:
    1. #include<vector>
    2. #include<string>
    3. #include<algorithm>
    4. #include<cassert>
    5. #include<stdio.h>
    6. //------------------------------------------------------------------------------
    7. typedef std::vector<int> Tuple;
    8.  
    9. //------------------------------------------------------------------------------
    10. int choose( int n, int k )
    11. {
    12.     /// Get C(n,k), the number of choices (combinations), i.e. k-subsets
    13.     /// of an n-set.
    14.  
    15.     if (k > n) return 0;
    16.     if (k * 2 > n) k = n-k;
    17.     if (k == 0) return 1;
    18.  
    19.     int result = n;
    20.     //int i;
    21.     for( int i = 2; i <= k; ++i ) {
    22.         result *= n - i + 1;
    23.         result /= i;
    24.     }
    25.     return result;
    26. }
    27.  
    28. //------------------------------------------------------------------------------
    29. void combination(int* c,int n,int p, int x)
    30. {
    31.     ///  Get the x-th lexicographically ordered set of p numbers in range [1,n]
    32.     ///  Output is in c, and should be sizeof(int)* p
    33.  
    34.     int i,r,k = 0;
    35.     for(i=0;i<p-1;i++){
    36.         c[i] = (i != 0) ? c[i-1] : 0;
    37.         do {
    38.             c[i]++;
    39.             r = choose(n-c[i],p-(i+1));
    40.             k = k + r;
    41.         } while(k < x);
    42.         k = k - r;
    43.     }
    44.     c[p-1] = c[p-2] + x - k;
    45. }
    46.  
    47. //------------------------------------------------------------------------------
    48. void list_permutation(std::vector<Tuple>& L, int n, int k)
    49. {
    50.     /// List all permutations of k integers chosen from [0,n)
    51.     /// to L.
    52.  
    53.     assert(L.size() == 0);
    54.     int const C = choose(n,k);
    55.     int p[k];
    56.     for(int x = 1; x <= C; x++) {
    57.         combination(p,n,k,x);
    58.         for(int h=0; h < k; h++) { p[h]--; }
    59.         do {
    60.             Tuple t(p,p+k);
    61.             L.push_back(t);
    62.         } while( std::next_permutation(p,p+k) );
    63.     }
    64. }
    65.  
    66. //------------------------------------------------------------------------------
    67. void print_table( void const *data,
    68.                   std::vector<Tuple> const rowTit,
    69.                   std::vector<Tuple> const colTit ){
    70.     printf("%5s"," ");
    71.     for( size_t jj = 0; jj < colTit.size(); jj++){
    72.         char f[10] = {0};
    73.         std::string s;
    74.         for( size_t j = 0; j < colTit[jj].size(); j++ ){
    75.             sprintf(f,"%d", colTit[jj][j]);
    76.             s.append(f);
    77.         }
    78.         printf("%-4s",s.c_str());
    79.     }
    80.     printf("\n");
    81.  
    82.     for(size_t ii = 0; ii < rowTit.size(); ii++) {
    83.         for( size_t i = 0; i < rowTit[ii].size(); i++ ){
    84.             printf("%d", rowTit[ii][i]);
    85.         }
    86.         printf(" ");
    87.  
    88.         for( size_t jj = 0; jj < colTit.size(); jj++) {
    89.             printf("%4d", ((int const*)data)[colTit.size()*ii + jj]);
    90.         }
    91.         printf("\n");
    92.     }
    93. }
    94. //------------------------------------------------------------------------------

    Thí dụ
    C++ Code:
    1. int main()
    2. {
    3.     int prima[32] = {13, 5, 6, 1, 2, 7, 4, 3, 0, 8,11,12,15,14,10, 9,21,22,17,18,23,20,19,16,24,27,28,31,30,26,25,29};
    4.     alt_analyze(prima);
    5. }

    Nội dung hiển thị trên màn hình
    Code:
         01  10  02  20  12  21
    01   36  36  24  24  24  24
    10   36  36  24  24  24  24
    02   24  24  24  24  16  16
    20   24  24  24  24  16  16
    03   24  24  24  24  16  16
    30   24  24  24  24  16  16
    04   24  24  24  24  16  16
    40   24  24  24  24  16  16
    12   24  24  16  16  24  24
    21   24  24  16  16  24  24
    13   24  24  16  16  24  24
    31   24  24  16  16  24  24
    14   24  24  16  16  24  24
    41   24  24  16  16  24  24
    23   16  16  16  16  16  16
    32   16  16  16  16  16  16
    24   16  16  16  16  16  16
    42   16  16  16  16  16  16
    34   16  16  16  16  16  16
    43   16  16  16  16  16  16
         012 021 102 120 201 210
    012  144 144  96  64 144  96
    021   96 144 144  96 144  64
    102   96  64 144 144  96 144
    120  144  96  96 144  64 144
    201   64  96 144 144 144  96
    210  144 144  64  96  96 144
    013  144 144  96  64 144  96
    031   96 144 144  96 144  64
    103   96  64 144 144  96 144
    130  144  96  96 144  64 144
    301   64  96 144 144 144  96
    310  144 144  64  96  96 144
    014  144 144  96  64 144  96
    041   96 144 144  96 144  64
    104   96  64 144 144  96 144
    140  144  96  96 144  64 144
    401   64  96 144 144 144  96
    410  144 144  64  96  96 144
    023   96  96  96  64  96  64
    032   96  96  96  64  96  64
    203   64  64  96  96  96  96
    230   96  96  64  96  64  96
    302   64  64  96  96  96  96
    320   96  96  64  96  64  96
    024   96  96  96  64  96  64
    042   96  96  96  64  96  64
    204   64  64  96  96  96  96
    240   96  96  64  96  64  96
    402   64  64  96  96  96  96
    420   96  96  64  96  64  96
    034   96  96  96  64  96  64
    043   96  96  96  64  96  64
    304   64  64  96  96  96  96
    340   96  96  64  96  64  96
    403   64  64  96  96  96  96
    430   96  96  64  96  64  96
    123   96  64  96  96  64  96
    132   96  64  96  96  64  96
    213   96  96  64  64  96  96
    231   64  96  96  96  96  64
    312   96  96  64  64  96  96
    321   64  96  96  96  96  64
    124   96  64  96  96  64  96
    142   96  64  96  96  64  96
    214   96  96  64  64  96  96
    241   64  96  96  96  96  64
    412   96  96  64  64  96  96
    421   64  96  96  96  96  64
    134   96  64  96  96  64  96
    143   96  64  96  96  64  96
    314   96  96  64  64  96  96
    341   64  96  96  96  96  64
    413   96  96  64  64  96  96
    431   64  96  96  96  96  64
    234   64  64  64  64  64  64
    243   64  64  64  64  64  64
    324   64  64  64  64  64  64
    342   64  64  64  64  64  64
    423   64  64  64  64  64  64
    432   64  64  64  64  64  64
    Verdict: PASS
    Đã được chỉnh sửa lần cuối bởi Ada : 27-06-2021 lúc 09:57 AM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn