Siêu trí tuệ: tìm số nguyên tố hay là tăng minh bạch cho ngành đánh đề

Tôi mới xem chương trình Siêu trí tuệ Việt Nam tập 7. Ban tổ chức cho một ma trận 1380 số, trong đó có 7 số nguyên tố. Có 4 số nguyên tố sẽ tạo thành cặp 2 đường thẳng vuông góc. Người chơi phải tìm ra chỗ giao nhau của hai đường thẳng này, hình như không giới hạn thời gian.

Thử thách này nghe qua thì thấy khó, nhưng xem kỹ thì không phải vậy. Người chơi không cần phải kiểm thử 1380 số mà có thể sử dụng mẹo/thuật toán để nhanh chóng loại bỏ hợp số và khoanh vùng vị trí của số bí mật. Ban tổ chức dùng nhiều hiệu ứng khiến người coi có cảm giác ma trận số được chọn ngẫu nhiên, nhưng, không biết vì vô tình hay vì thiếu... trí tuệ, họ đã chọn một đề bài dễ hơn rất nhiều.

Tôi nhẩm tính (xem bên dưới) thì thấy đối với đề bài mà ban tổ chức đã ra, để tìm được số bí mật người chơi chỉ cần kiểm thử cỡ 44 trong tổng số 1380 số, tức là độ khó của bài toán này chỉ bằng 1/30 so với cảm nhận ban đầu. Để kiểm thử một số thì chỉ cần kiến thức cấp 2, mất trung bình 30 giây. Tôi nghĩ sẽ mất chừng 20 phút để hoàn thành thử thách.

Thuật toán mà tôi sử dụng không tìm hết cả 7 số nguyên tố, mà chỉ tìm bộ 4 số tạo thành 2 đường thẳng vuông góc. Bạn sinh viên tìm được cả 7 số nguyên tố, nên sẽ mất thời gian hơn. Nhưng nếu để ý bạn sẽ thấy ban tổ chức một lần nữa đã "giúp" bạn sinh viên khoanh vùng các số nguyên tố. Nếu bạn vẽ hình chữ nhật nhỏ nhất có chứa 4 số nguyên tố tạo thành 2 đường thằng vuông góc, bạn sẽ thấy 3 số còn lại cũng nằm trong hình chữ nhật này. Tôi chưa tính ra xác suất cụ thể, nhưng một đề bài ngẫu nhiên khó lòng có tính chất này và do đó sẽ khó hơn.

Có thể thấy rằng độ khó của bài toán phụ thuộc vào việc các số trong ma trận và vị trí của các số nguyên tố có được chọn ngẫu nhiên hay không. Việc này là do một phần mềm quyết định, nhưng hiện giờ phần mềm đó do ban tổ chức tạo ra và chạy trên phần cứng của họ. Khán giả có quyền nghi ngờ ban tổ chức đã thay đổi phần mềm/phần cứng để chọn đề bài như họ mong muốn. Ngược lại, ban tổ chức cũng có nhu cầu chứng minh rằng phần mềm/phần cứng của họ đã tạo số ngẫu nhiên đúng như kỳ vọng.

Ở đây có một câu hỏi rất thú vị: có cách nào thiết kế hệ thống tạo số ngẫu nhiên công bằng, đảm bảo không ai có thể ảnh hưởng đến kết quả?

Đây là câu hỏi tỉ đô. Trả lời được nó không chỉ giúp cuộc thi Siêu trí tuệ trí tuệ siêu hơn nữa, mà còn góp phần tăng minh bạch cho ngành đánh đề truyền thống của nước nhà. Khi bạn chơi đề, làm sao bạn biết công ty xổ số đã chọn kết quả một cách ngẫu nhiên? Tương tự, làm sao bạn biết Vietlott không ăn gian, chọn số trúng theo một danh sách cho trước? Vietlott chọn số bằng máy tính, lỡ họ bị hack thì sao?

Trong bài sau tôi sẽ bàn về một số giải pháp. Hãy để lại còm nếu bạn có lời giải hoặc câu hỏi.

----

Tìm số bí mật như thế nào?

Dưới đây là cách giải của tôi. Nếu bạn biết cách nào ít tốn thời gian hơn xin để lại còm.

I. Loại bỏ hợp số

1/ Ai để ý sẽ thấy các số trong mạ trận đều nhỏ hơn 20.000 và các số nguyên tố đều nhỏ hơn 10.000. Như vậy người chơi có thể ngay lập tức loại bỏ 50% các số đã cho.

2/ Trong 50% còn lại, 60% sẽ có tận cùng là 0, 2, 4, 6, 8, hoặc 5. Những số này là hợp số, có thể loại ngay lập tức, tức chỉ cần kiểm thử 50% * 40% = 20% các số đã cho.

3/ Trong 20% số còn lại, 1/3 sẽ có tổng các chữ số chia hết cho 3, tức là số đó sẽ chia hết cho 3 và không phải là số nguyên tố. Tức là chỉ cần kiểm thử chưa đến 14% các số đã cho.

II. Khoanh vùng số bí mật

1/ Quét theo các cột của ma trận, từ trái sang phải, mỗi cột từ trên xuống dưới.

2/ Khi tìm được một số nguyên tố, kiểm thử những số nằm cùng hàng. Nếu tìm được một số nguyên tố khác trong cùng một hàng, ngay lập tức có thể loại bỏ được tất cả các cột nằm ở bên tay phải số nguyên tố thứ hai vừa tìm được.

3/ Hàng vừa tìm được sẽ chia ma trận thành hai phần, chọn phần nhỏ hơn để tìm các số nguyên tố còn lại, bằng cách quét từng hàng.

4/ Khi tìm được một số nguyên tố, kiểm thử những số nằm cùng cột. Nếu tìm được một số nguyên tố khác trong cùng một cột thì sẽ tìm được bí mật.

Với chiến thuật này thì trung bình mà nói người chơi chỉ cần quét 3/4 diện tích ma trận. Trong trường hợp may mắn, ví dụ như số nguyên tố nằm trên một cột lệch hẳn về tay trái (hoặc tay phải), người chơi có thể chỉ cần quét một phần diện tích rất nhỏ của ma trận ban đầu.

III. Kiểm thử số nguyên tố

Phần khó nhất của đề bài là kiểm thử số nguyên tố, nhưng phần này cũng không quá khó như tưởng tượng. Để kiểm thử số nhỏ hơn 10.000, người chơi không cần phải chia từ 1 cho đến 10.000, mà chỉ cần kiểm tra xem nó có chia hết cho 25 số nguyên tố nhỏ hơn 100. Tôi kiểm thử ngẫu nhiên khoảng 20 số trong ma trận mà ban tổ chức chọn thì thấy số nào cũng có ước số nhỏ hơn 50. Tức là người chơi chỉ cần học thuộc luật chia hết của 12 số nguyên tố nhỏ hơn 50 (ngoại trừ 2, 3 và 5).