Math Labs

Bài 5

Xét hệ pp phương trình với q=2pq=2p ẩn x1,…,xqx_1,\ldots,x_q, trong đó mọi hệ số aija_{ij} đều thuộc {−1,0,1}\{-1,0,1\}. Chứng minh rằng hệ có một nghiệm sao cho (a) mọi xjx_j đều là số nguyên; (b) ít nhất một xj≠0x_j\ne0; (c) ∣xj∣≤q|x_j|\le q với mọi jj.
Bước 1 trên 5: Đếm các vectơ khác không bị chặn
Bước trướcBước tiếp
Hiểu nôm na

Hộp [0,q]q[0,q]^q cung cấp nhiều vectơ ứng viên, trong khi các phương trình chỉ có thể tạo ra một số hữu hạn bộ giá trị đầu ra.

Nvec=(q+1)q−1>(q2+1)p,q=2pN_{\mathrm{vec}}=(q+1)^q-1>(q^2+1)^p,\quad q=2p
Phân tích chi tiết

Đặt q=2pq=2p. Xét tất cả các vectơ nguyên khác không (x1,…,xq)(x_1,\ldots,x_q) sao cho 0≤xi≤q0\le x_i\le q. Có (q+1)q−1(q+1)^q-1 vectơ như vậy. Ta sẽ ánh xạ mỗi vectơ vào bộ pp vế trái của các phương trình.