MathLabs

Bài 5

Cho nn là một số nguyên dương. Một cặp bộ nn số (a1,…,an)(a_1,\ldots,a_n) và (b1,…,bn)(b_1,\ldots,b_n) với các phần tử nguyên được gọi là tinh tế nếu ∣a1b1+⋯+anbn∣≤1|a_1b_1+\cdots+a_nb_n|\le1. Xác định số lượng lớn nhất các bộ nn số phân biệt với các phần tử nguyên sao cho hai bộ bất kỳ trong chúng tạo thành một cặp tinh tế.
Bước 4 trên 5: Chia một họ tinh tế theo vị trí khác không cuối cùng
Bước trướcBước tiếp
A=A1∪⋯∪An,Ai={tuples whose last nonzero entry is at position i},∣Ai∣≤2iA=A_1\cup\cdots\cup A_n,\quad A_i=\{\text{tuples whose last nonzero entry is at position } i\},\quad |A_i|\le2i
Phân tích chi tiết

Gọi AA là một tập các bộ khác không sao cho hai bộ bất kỳ trong đó đều tinh tế. Viết A=A1∪A2∪⋯∪AnA=A_1\cup A_2\cup\cdots\cup A_n, trong đó AiA_i là tập các bộ trong AA có phần tử khác không cuối cùng ở vị trí ii. Chỉ cần chứng minh ∣Ai∣≤2i|A_i|\le2i với mọi ii, vì 2+4+⋯+2n=n2+n2+4+\cdots+2n=n^2+n, nên cùng với bộ không điều này chặn ∣A∣+1≤n2+n+1|A|+1\le n^2+n+1.