Dùng nguyên lí Dirichlet để giải bài toán tổ hợp - Phần 2

Bài toán: Tìm số tự nhiên n lớn nhát sao cho tồn tại n số nguyên không âm $x_1,x_2,..x_n$ không đồng thời bằng 0, sao cho với mọi $\varepsilon _1, \varepsilon _2,..\varepsilon _n$ $\in$ {-1;0;1} không đồng thời bằng 0 sao cho $n^3$ không chia hết cho $\varepsilon _1x_1+\varepsilon _2x_2+..\varepsilon _nx_n$

Lời giải.

Với n=9 ta chọn $1,2,2^2,..2^8$

Khi đó: $| \varepsilon _1+..+2^9\varepsilon _9|\le 1+2+..2^8<9^3$

Nếu $n\ge10$ không mất tính tổng quát, giả sử $n=10$ khi đó số tập con của S={$x_1,x_2,..z_10$} là $2^{10}$ và vì $2^{10}>10^3$ nên theo nguyên lí Dirichlet tồn tại hai tập A và B là tập con của S sao cho tổng các phần tử của A có cùng số dư với tổng các phần tử của B.

Khi đó đặt $\varepsilon _i=1$ nếu $x_i$ thuộc A nhưng không thuộc B, $\varepsilon _i=-1$ nếu $x_i$ thuôc B nhưng không thuộc A, bằng 0 trong trường hợp còn lại khi đó:

$\sum \varepsilon _ix_i \vdots n^3$