hiểu logic chương trình xổ số theo skiena

Question

Tôi đang đọc bài viết từ vị trí sau. Đây là tài liệu dạng đoạn văn bản.

Link

Vấn đề của việc tìm kiếm một tập tối thiểu là vé đó sẽ đảm bảo một chiến thắng không phải là một tầm thường. Cho rằng P trong số R kết quả sẽ là từ bộ phận bói toán, không khó để thấy rằng có NCP = (N/P!)/(N-P)! có thể P-tập con từ tập tài sản có thể xảy ra trong vé thắng. Nếu chúng tôi chọn tất cả các tập con P từ nhân viên bói toán được đặt W lần và điền vào các khe RP còn lại tùy ý, tập vé nhận được sẽ có ít nhất W lần xuất hiện của mỗi tập con P và đảm bảo W thắng . Tuy nhiên, một tập hợp như vậy không cần phải là tối thiểu và trong hầu hết các trường hợp thì không.

Chúng tôi biết từ lời hứa của thầy bói rằng một trong các P-tập hợp con sẽ xảy ra trong vé thắng. Có thể cho hai P-tập hợp con đến khác nhau ít hơn số J. Khi tình huống như vậy phát sinh, các tập hợp con được cho là chồng lên nhau hoặc che phủ lẫn nhau đối với các số J được chia sẻ và chỉ một trong các tập con P phải nằm trong vé mua . Hiện tượng này được minh họa tốt nhất bằng cách sử dụng một ví dụ. Giả sử chúng tôi đang chơi xổ số PICK-4 và yêu cầu một chiến thắng 2/4. Do đó R = 4, J = 2 và W = 1. Hơn nữa, giả sử rằng người thầy bói dự đoán 3 số từ một tập hợp gồm 5 số (ví dụ: P = 3 và N = 5). Nếu tất cả P-tập con được lấy từ bộ phận bói toán và tự ý điền để hoàn thành vé, chúng tôi sẽ có một bộ mười vé đảm bảo một chiến thắng 2/4 (Xem Hình 1). Tuy nhiên, cũng có thể là để loại trừ một số vé khỏi tập hợp này vì một số chồng chéo gồm hai số . Ví dụ, tập hợp con {3, 4, 5} khác nhau so với {1, 3, 5} chỉ bằng một số và sẽ lãng phí khi sử dụng cả hai trong số này trong vé đã mua. Chúng tôi có thể nghĩ rằng không bao gồm {3, 4, 5} sẽ cho phép khả năng mất, nhưng đó không phải là trường hợp vì nếu {3, 4, 5} xảy ra, chúng tôi sẽ có '3' và '5' trong { 1, 3, 5} mà chúng tôi đã mua để nhận giải thưởng! Tương tự như vậy có thể có nhiều tập hợp con Pdư thừa hơn. Một giải pháp tối ưu được thể hiện trong Hình 2. Xổ số của chúng tôi vấn đề là tìm tập nhỏ nhất các tập con P từ bộ biên dịch viên số đảm bảo số chiến thắng được chỉ định bằng cách giữ số lượng trùng lặp ở mức tối thiểu. Tập hợp các tập con P- này xác định tập hợp chiến thắng bất kể số nào được sử dụng để hoàn tất các khe R trên vé.

Câu hỏi của tôi được followiong

1. Như tác giả metioned "Nếu tất cả P-tập con được lấy từ các thầy bói thiết lập và tùy tiện điền để hoàn vé, chúng tôi sẽ có một bộ mười vé "Như trong bảng bài viết là thiếu có thể bất kỳ một trong những giúp tôi ở đây 10 vé là gì?

2. Trong ví dụ trên nếu xảy ra 1 và 3 và nếu chúng tôi không chọn {1, 3, 5} thì chúng ta có thể giành chiến thắng ở đây như thế nào?

3. Có ai có thể tìm ra hình 2 bị thiếu trong bài viết không?

cảm ơn!

Answer 1

1. Dưới đây là một danh sách inefficent 10 vé

   {1, 2, 3, 6} 
   {1, 2, 4, 6} 
   {1, 2, 5, 6} 
   {1, 3, 4, 6} 
   {1, 3, 5, 6} 
   {1, 4, 5, 6} 
   {2, 3, 4, 6} 
   {2, 3, 5, 6} 
   {2, 4, 5, 6} 
   {3, 4, 5, 6} 
   

2. Mu. Để giành chiến thắng chúng ta cần phải phù hợp với 2 trong số 4. Vì vậy, nó không phải là trường hợp 1 và 3 xảy ra, đó là trường hợp mà một tập hợp cụ thể của 3 xảy ra và chúng tôi chỉ cần phải phù hợp với 2 người trong số họ.

3. Tôi nghĩ điều này là tối ưu.

   {1, 2, 3, 4} 
   

Nhưng tôi không hoàn toàn tích cực mà tôi có thể chọn 4. Nếu tôi chỉ được phép chọn 3 mỗi vé sau đó một bộ tối ưu sẽ là:

{1, 2, 3} 
    {2, 3, 4} 

Answer 2

Hai vé là:

{1, 3, 5, X}

{2, 4, 5, X}

trong đó X là số được chọn tùy ý không ảnh hưởng đến giải pháp.