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).

Comments

Việt said…
Oh oh, sau bài này thì số lượng người tin vào vietlot sẽ còn tăng thêm nhiều nhiều anh Thái à.
Quang Nguyễn said…
Viettlot quay số bằng lồng quay chứ đâu phải máy tính đâu a Thái
Thai Duong said…
Quang Nguyễn: đúng như bạn nói, Vietlott quay số bằng lồng quay, tôi mới xem ở https://www.youtube.com/watch?v=2ZGe-2ZPdSM. Tôi cứ ngỡ họ quảng cáo "xổ số điện toán" thì họ sẽ làm bằng máy tính, lỗi của tôi.

Tôi xem cách quay bằng lồng của họ thì không hiểu họ đảm bảo công bằng như thế nào nhỉ? Tôi không hiểu cơ chế hoạt động của cái lồng quay. Nếu biết xin bạn chỉ giùm. Cảm ơn nhiều!
Quay bằng lồng thì mới control được chứ. Để mà ngẫu nhiên 100% thì nổ jackpot suốt ngày à :))
Chan Le said…
BTC chắc ko biết algorithm, hoặc perhaps 2 cái đường vuông góc ko nhất thiết phải nằm ngang và dọc?
nhưng phần khó chắc là chạy cái thuật toán trên trong đầu hoàn toàn :-? ko có giấy bút gì ngồi track, xài trí nhớ như RAM thì cũng khoai mà :))
Quang Nguyễn said…
Em cũng ko chắc là quay bằng lồng thì có ăn gian hay không nữa anh Thái ơi. Nhưng nếu xét về khía cạnh kinh tế như sau: giả sử lượng mua đạt được 8,5 triệu lượt vé, con số này lớn hơn xác suất trúng giải mega 6/45 (45!/(6!*(45-6)!) = 8.145.060). Thực tế thì khoảng 1 tuần mới có 1 giải khoảng 50 tỷ của mega 6/45 được nổ. Trung bình 1 ngày cần 1 triệu lượt vé được bán ra, 1 người mua khoảng 2 vé thì 1 ngày cần nữa triệu người tham gia, mà dân ta cũng đam mê vé số nên ko khó để bán được lượng vé này). Như vậy, thì 80 tỷ thu vào, chi ra 50 tỷ + 10 tỷ chi phí vận hành thì còn lãi 20 tỷ. Giả sử đúng vậy thì xét về bài toán kinh tế thì ko nên ăn gian làm gì (vì đang vận hành có lãi). Còn nếu ít người chơi quá và lượng vé ko bán được như vậy thì khả năng cao là lồng quay này dễ bị "hack" và lồng quay này sẽ ko có "tư tưởng vững vàng hoặc ko còn ngẫu nhiên".
RacTun said…
Tôi nghe nói, LỒNg quay cầu xổ số của trung quốc, có thể control được như mấy casino control con xúc sắc. Ai giải ngố giúp tôi.
độ nặng của các quả bóng sẽ là mấu chốt ...
Thai Duong said…
>BTC chắc ko biết algorithm, hoặc perhaps 2 cái đường vuông góc ko nhất thiết phải nằm ngang và dọc?

Lúc nào cũng nằm ngang và dọc. BTC không biết algorithm thì mới nói là BTC có vẻ hơi thiếu trí tuệ.


>nhưng phần khó chắc là chạy cái thuật toán trên trong đầu hoàn toàn :-? ko có giấy bút gì ngồi track, xài trí nhớ như RAM thì cũng khoai mà :))

Chỉ cần nhớ vị trí của 4 số thôi, đâu có cần nhớ nhiều đâu. Tốn rất ít RAM, tốn CPU nhiều hơn, nhưng mấy phép chia trial cũng là với số nhỏ thôi.

Thai Duong said…
>Em cũng ko chắc là quay bằng lồng thì có ăn gian hay không nữa anh Thái ơi. Nhưng nếu xét về khía cạnh kinh tế như sau: giả sử lượng mua đạt được 8,5 triệu lượt vé, con số này lớn hơn xác suất trúng giải mega 6/45 (45!/(6!*(45-6)!) = 8.145.060). Thực tế thì khoảng 1 tuần mới có 1 giải khoảng 50 tỷ của mega 6/45 được nổ. Trung bình 1 ngày cần 1 triệu lượt vé được bán ra, 1 người mua khoảng 2 vé thì 1 ngày cần nữa triệu người tham gia, mà dân ta cũng đam mê vé số nên ko khó để bán được lượng vé này). Như vậy, thì 80 tỷ thu vào, chi ra 50 tỷ + 10 tỷ chi phí vận hành thì còn lãi 20 tỷ. Giả sử đúng vậy thì xét về bài toán kinh tế thì ko nên ăn gian làm gì (vì đang vận hành có lãi). Còn nếu ít người chơi quá và lượng vé ko bán được như vậy thì khả năng cao là lồng quay này dễ bị "hack" và lồng quay này sẽ ko có "tư tưởng vững vàng hoặc ko còn ngẫu nhiên".

Phân tích hay, cảm ơn bạn.

Thường các vụ ăn gian đến từ nhân viên.
Chan Le said…
Quay bằng lồng cheat đc đấy - mình coi đâu đó có trò làm tránh banh nặng/ nhẹ hơn hay sơn iron powder lên rồi bật nam châm cho nó dính sau 1 hồi quay

Còn máy quay random thì có đại ca này https://www.nytimes.com/interactive/2018/05/03/magazine/money-issue-iowa-lottery-fraud-mystery.html
Chan Le said…
Riêng cái siêu trí tuệ thì có vẻ thí sinh cũng thật thà - khúc cuối chỉ ra đc hết 7 số nên chắc là cũng ko biết algorithm và ngồi ... chia hết thật :|
buivd said…
Cách giải quyết anh Thái đã bàn, lại bàn về cách ra đề như thế nào.
- giả sử để làm khó thí sinh, đề bài chọn số có 4-5 chữ số, tức là trong khoảng 1000-20.000
- để có chính xác 7 số nguyên tố xuất hiện trong 1380 số, đơn giản nhất là chọn 7 số trước, sao đó chọn 1373 hợp số. vấn đề vì sao các số nguyên tố được chọn ở đây lại nhỏ hơn 10.000 vẫn chưa rõ ràng (có thể do btc “thương” thí sinh đỡ phải tính nhiều)
- chọn 1373 hợp số: tạm gọi tập các hợp số dễ nhận biết là H, tập này chứa các số kết thúc là số 0,2,4,5,6,8 và các số có tổng chữ số chia hết cho 3. có thể thấy tập H này chiếm quá bán, do đó nếu lấy phân bố đều thì “cảm giác” có lợi cho thí sinh hơn (số hợp số thuộc H càng ít thì càng khó, thí sinh phải tính toán nhiều hơn)
- chọn cách đặt 7 số nguyên tố vào vị trí: phải kiểm soát được sự “nhập nhằng” trong đề bài, có thể vô tình tạo ra cách cặp vuông góc nhưng không nằm cùng hàng ngang/dọc mà không kiểm soát được. Giả sử chọn 4 điểm làm 4 điểm cần tìm. chọn 4 điểm này tạo thành một hình chữ nhật (theo lập luận của anh Thái). Hình chữ nhật này nếu nhỏ hoặc to thì diện tích bên trong hoặc ngoài sẽ lớn hơn phần còn lại. Nếu đặt ngẫu nhiên 3 điểm còn lại vào các vị trí thoả mãn tkhông tạo thành các đường vuông góc với 4 điểm cho trước, thì khả năng các điểm trong 3 điểm này rơi vào phần diện tích lớn hơn “cảm giác” sẽ cao hơn. Tuy nhiên đối với chương trình, có thể thấy rằng tuy phần diện tích bên trong nhỏ hơn bên ngoài hình chữ nhật, nhưng cả 3 điểm còn lại đều rơi vào bên trong, điều này có thể xảy ra nhưng với khả năng thấp 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
-> nếu chọn ngẫu nhiên, khả năng đề bài dễ vẫn có thể xảy ra. em nghĩ khẳng định của anh Thái đúng khi thực hiện nhiều lần ra đề và tính toán độ khó trung bình của các đề. Với 1 lần ra đề, btc sẽ, chẳng hạn, sinh ngẫu nhiên đề bài cho tới khi đề bài đạt đủ một vài tiêu chí về độ khó nào đó...
em nghĩ btc có lý do của họ khi đưa ra đề bài, tuy nhiên có thể nó chưa đủ hay (và thiếu thuyết phục ở vài chỗ).
Xổ số tại Việt Nam đều được dậy qua một trường lớp chuyên nghiệp đó là ảo thuật.
Unknown said…
1 số 4 chữ số chia thành 4 cái khoá ứng với từng hàng(000x), đứng quay từng khoá từ 1>9, chưa cần đọc đề, vào quay luôn cao nhất 1 phút 😅
Việt Nguyễn said…
Mấy cái chương trình này nó dàn dựng hết rồi, có đề cương vs công thức cho mà đọc. Nó phát lên kiếm tiền quảng cáo chứ gì.