Chứng minh rằng không thể chia 1 tập hợp gồm 18 số tự nhiên liên tiếp thành 2 tập hợp A,B rời nhau sao cho tích A = tích B
Chứng minh rằng không thể chia 1 tập hợp gồm 18 số tự nhiên liên tiếp thành 2 tập hợp A,B rời nhau sao cho tích A = tích B
Đáp án:
Giải thích các bước giải:
Giả sử chúng ta chia được một tập `S=n,n+1,…n+17` của `18` số nguyên dương liên tiếp thành tập `A, B` sao cho \(\prod_{n \in A}a=\prod_{n \in B}b\) và tách của các phần tử trong A bằng tích của các phần tử trong B, nếu 1 tập chứa bội số của 19 thì tập còn lại cũng như thế.
Do vậy, S không chứa bội số nào của 19 hoặc chứa ít nhất hai bội số của 19. Vì có duy nhất 1 trong 18 số nguyên dương liên tiếp có thể là bội của 19, S phải không chứa bội số nào. Bởi vậy `n,n+1,…n+17` lần lượt đồng dư `1,2,3,…,18\ mod\ 19` (chia lấy dư). Do vậy, theo quy tắc Wilson:
\(\prod_{n \in A}a \times \prod_{n \in B}b=n(n+1)+…(n+17)=18!=-1\ (mod\ 19)\)
Tuy nhiên hai tích của bên trái bằng nhau, điều này không có khả năng vì `-1` không là bình phương của phép mod 19. Bởi vậy, không tồn tại hai tập A và B