Vòng chung kết $\mathsf{UEFA}\;\mathsf{EURO}$ diễn ra năm nay vẫn giữ nguyên thể thức gồm $24$ đội, chọn ra $2$ đội dẫn đầu mỗi bảng đấu với $4$ đội đứng ngay sau có kết quả tốt nhất bước vào vòng $16$ đội. Ta có $4/6$ cặp đấu có sự xuất hiện của đội dẫn đầu mỗi bảng như sau
$$\begin{matrix} \mathsf{1B}\vee \mathsf{3A}/\mathsf{D}/\mathsf{E}/\mathsf{F} & \mathsf{1C}\vee \mathsf{3D}/\mathsf{E}/\mathsf{F}\\ \mathsf{1F}\vee \mathsf{3A}/\mathsf{B}/\mathsf{C} & \mathsf{1E}\vee \mathsf{3A}/\mathsf{B}/\mathsf{C}/\mathsf{D} \end{matrix}$$
Chứng minh không tồn tại cách match-ups nào khoa học hơn.
Edit (7/8). Đây là cách của mình. Mình sẽ sử dụng qubit vào đây và bắt đầu với bài toán trực quan hơn:
Hall's Marriage. Có $2$ cặp khách mời tham gia ghép đôi, nhận ra bạn nữ $\mathsf{A}$ thích anh $\mathsf{C}$ và anh $\mathsf{D}$ còn bạn $\mathsf{B}$ thích duy chỉ anh $\mathsf{D}.$ Vậy lựa chọn tốt nhất ở đây là $\mathsf{A}$ chọn $\mathsf{C}$ và $\mathsf{B}$ chọn $\mathsf{D}.$ Còn đây là dưới con mắt toán học:
Nếu $\mathsf{A}$ không biết được suy nghĩ của $\mathsf{B}$ thì $\mathsf{A}$ cần cân nhắc lựa chọn cho mình hơn $1$ khả năng, trạng thái $11.$ Còn $\mathsf{B}$ thì $\mathsf{B}$ chỉ có $1$ lựa chọn, trạng thái $01.$ Giả sử $\mathsf{A}$ ích kỉ không quan tâm đến $\mathsf{B}$ mà chọn trước, lúc này $11\rightarrow 01.$ Và nhỡ đâu $\mathsf{A}$ chọn $\mathsf{D}$ thì còn lại $\mathsf{B}$ và $\mathsf{C},$ đây là khả năng $\mathsf{B}$ không lường trước được, trạng thái $01\rightarrow 10.$ Vậy trạng thái $10$ có thỏa mãn không, tất nhiên là không, mình gọi như vậy đều có cái lí hết vì $1\Rightarrow 1, 0\Rightarrow 1, 0\Rightarrow 0$ theo logic đều đúng chỉ có $1\Rightarrow 0$ là sai thôi (và cũng vì mình là người làm việc với cơ số $2$ và $10$ thường xuyên). Tóm lại $11\oplus 01\rightarrow\mathsf{unknown}$ có thể là $10$ hoặc $01.$ Giải quyết trọn vẹn nó bằng cách trạng thái hóa $01\rightarrow 00.$ Hoàn toàn đúng vì theo logic là $\mathsf{true}\Rightarrow\mathsf{true}.$ Dẫn đến $11\oplus 01\rightarrow 11\oplus 00\rightarrow 11.$ Bài toán này khi biểu diễn trên mô hình:
$$\begin{matrix}\mathsf{pairs} & A & B\\ C & & \times\\ D & & \end{matrix}$$
$$\begin{matrix}\mathsf{pairs} & A & B\\ C & & \times\\ D & & \checkmark\end{matrix}$$
$$\begin{matrix}\mathsf{pairs} & A & B\\ C & & \times\\ D & \times & \checkmark\end{matrix}$$
Nên ngay từ đầu ta giới hạn lựa chọn của $\mathsf{A}$ chỉ mỗi $\mathsf{C}$ là được. Quay trở lại với bài toán..
Combinations of matches. Cũng biểu diễn trên mô hình:
$$\begin{matrix}\mathsf{match-ups} & B & C & E & F\\ A & & \times & & \\ B & \times & \times & & \\ C & \times & \times & & \\ D & & & & \times\\ E & & & \times & \times\\ F & & & \times & \times\end{matrix}$$
Còn $14$ ô ở trạng thái $11.$ Và nhận thấy ở bất cứ hàng nào cũng có hơn $1$ lựa chọn, bất cứ cột nào cũng có hơn $2$ lựa chọn (vì chỉ có $4/6$ hàng được chọn). Không giảm tổng quát chỉ xét với cột $\mathsf{E}, \mathsf{F}$ và trong trường hợp bỏ đi hàng $\mathsf{A}, \mathsf{B}$ là khó nhất, có được:
$$\begin{matrix}\mathsf{match-ups} & E & F\\ C & & \\ D & & \times\end{matrix}$$
Đó chính là bài toán gốc phía trên, xem như $1$ nhánh của dạng bài toán thỏa mãn "envyfree." Xem thêm_ https://diendantoanh...e-1#entry729392, và đây nữa_ https://diendantoanh...ứ-khi-chỉ-biết/, cảm ơn các bạn.
Bài viết đã được chỉnh sửa nội dung bởi DOTOANNANG: 16-08-2021 - 15:02
