Chủ đề này có 4 trả lời

[Math04]

Một tập hợp các đường thẳng trong mặt phẳng được gọi là đẹp nếu các đường thẳng trong tập hợp này phân biệt, không có $3$ đường nào đồng quy và mỗi đường thẳng trong chúng đều có số các giao điểm của nó với tất cả các đường thẳng còn lại là một số lẻ. Tìm số $k$ nguyên dương nhỏ nhất sao cho với $2018$ đường thẳng phân biệt, không có $3$ đường nào đồng quy, bất kỳ, ta có thể bổ sung thêm $k$ đường thẳng để tạo thành tập hợp đẹp gồm $2018+ k$ đường thẳng.

[nhungvienkimcuong]

Một tập hợp các đường thẳng trong mặt phẳng được gọi là đẹp nếu các đường thẳng trong tập hợp này phân biệt, không có $3$ đường nào đồng quy và mỗi đường thẳng trong chúng đều có số các giao điểm của nó với tất cả các đường thẳng còn lại là một số lẻ. Tìm số $k$ nguyên dương nhỏ nhất sao cho với $2018$ đường thẳng phân biệt, không có $3$ đường nào đồng quy, bất kỳ, ta có thể bổ sung thêm $k$ đường thẳng để tạo thành tập hợp đẹp gồm $2018+ k$ đường thẳng.

Gọi $2018$ đường thẳng ban đầu là $d_1,d_2,\dots,d_{2018}$.

Vì lời giải sau thường xuyên thêm các đường thẳng mới $d_{2019},\dots,d_{n}$ nên cho tiện thì sẽ đặt tập hợp $X_n=\{d_1,d_2,\dots,d_{n}\}$. Gọi $g_n(i)$ là số giao điểm của $d_i$ với các đường thẳng khác thuộc $X_n$. 

Tiếp theo là phân hoạch $X_{2018}=\mathcal{D}_1\cup\mathcal{D}_2\cup\dots\cup\mathcal{D}_r$ trong đó $\mathcal{D}_u\cap \mathcal{D}_v=\varnothing$ với mọi $u\neq v$ và

$$d_i\parallel d_j\iff \exists t:d_i,d_j\in \mathcal{D}_t.$$

Sau này khi nói thêm đường thẳng mới $d'$ vào $\mathcal{D}_t$ nghĩa là $d'\parallel d$ với mọi $d\in \mathcal{D}_t$.

Kí hiệu các thứ như vậy là đủ rối rồi  , sau đây là lời giải.

 

$\bullet$ Chứng minh mọi tập hợp đẹp đều có chẵn đường thẳng. Từ đó suy ra $k$ chẵn.

Giả sử tồn tại tập hợp đẹp $\{d_1,d_2,\dots,d_n\}$ với $n$ lẻ. Vì $g_n(i)$ lẻ nên $\sum_{i=1}^ng_n(i)$ lẻ.

Mặt khác mỗi giao điểm thuộc đúng 2 đường thẳng nên tổng số giao điểm (chính là $\sum_{i=1}^ng_n(i)$) phải chẵn. Tới đây có được mâu thuẫn.

$\bullet$ Xây dựng một trường hợp không thỏa đề với $k=1008$.

Xét $2018$ đường thẳng thỏa mãn

$$X_{2018}=\mathcal{D}_1\cup\mathcal{D}_2\cup\dots\cup\mathcal{D}_{1009}$$

trong đó $|\mathcal{D}_i|=2$ với mọi $i=\overline{1,1009}$.

Khi đó thêm $1008$ đường thẳng mới bất kì thì sẽ tồn tại $i\in \{1,\dots,1009\}$ sao cho không có đường thẳng mới nào thuộc $\mathcal{D}_i$. Do vậy với $d_t\in \mathcal{D}_i$ thì $g_{2018+1008}(t)=g_{2018}(t)+1008$ chẵn. Như vậy không thể có tập hợp đẹp được.

$\bullet$ Chứng minh $k=1010$ thỏa đề.

Giả sử các tập hợp $|\mathcal{D}_i|$ chẵn với mọi $i\le m$ và $|\mathcal{D}_i|$ lẻ với mọi $m+1\le i\le r$, dễ thấy $m\le 1009$. Với mỗi $i\le m$, ta sẽ thêm một đường thẳng vào $\mathcal{D}_i$.

• Nếu $m$ chẵn thì đương nhiên $g_{2018+m}(t)$ lẻ với mọi $t=\overline{1,2018+m}$.
• Nếu $m$ lẻ, lúc này $g_{2018+m}(t)$ chẵn với mọi $t=\overline{1,2018+m}$. Ta sẽ thêm đường thẳng $d_{2018+m+1}$ sao cho đường thẳng này cắt tất cả $2018+m$ đường thẳng trước đó. Dẫn tới $g_{2018+m+1}(t)$ lẻ với mọi $t=\overline{1,2018+m+1}$.

Như vậy ở cả hai trường hợp thì ta thấy rằng sẽ thêm tối đa $m+1\le 1010$ đường thẳng mới để thu được tập hợp đẹp. Do vậy sẽ có những trường hợp chỉ thêm vào ít hơn $1010$ đường thẳng. 

Gỉa sử đã thêm vào $h<1010$ đường thẳng mới, khi đó $h$ chẵn. Ta có tập hợp đẹp đó là

\[X_{2018+h}=\mathcal{D}_1\cup\mathcal{D}_2\cup\dots\cup\mathcal{D}_{r}.\]

Thêm vào hai đường thẳng bất kì cùng thuộc $D_i$ nào đó thì $g_{2018+h+2}(t)$ lẻ với mọi $t=\overline{1,2018+h+2}$. Cứ thêm vào như vậy tới một lúc có được $1010$ đường thẳng mới để thu được tập hợp đẹp có $2018+1010$ đường thẳng.

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 22-08-2022 - 09:50

[hxthanh]

Thật sự mình chưa hiểu đề! Nếu chỉ thêm hai đường thẳng song song vào $\mathcal D_1$ có được không nhỉ?
Chẳng hạn $2017$ đường thẳng song song với $Ox$ một đường thẳng song song với $Oy$ thì có “đẹp” không?

[nhungvienkimcuong]

Chẳng hạn $2017$ đường thẳng song song với $Ox$ một đường thẳng song song với $Oy$ thì có “đẹp” không?

$2018$ đường thẳng này của thầy đẹp vì mỗi đường thẳng đều có số giao điểm là số lẻ.

 

Thật sự mình chưa hiểu đề! 

Ý đề bài là: Với $2018$ đường bất kì thì cần thêm ít nhất bao nhiêu đường thẳng để chắc chắn thu được tập đẹp.

 

Một đề bài khá tương tự: Tìm $k$ nguyên dương nhỏ nhất sao cho với 3 số nguyên bất kì $a,b,c$ thì có thể bổ sung thêm $k$ số nguyên $x_1,x_2,\dots,x_k$ sao cho

\[a^2+b^2+c^2+\sum_{i=1}^{k}x_i^2\equiv 0\pmod{3}.\]

Ta thấy rằng $a^2+b^2+c^2$ đồng dư $0,1$ hoặc $2$ theo modulo $3$. Trường hợp $a^2+b^2+c^2\equiv 1\pmod{3}$ thì không thể bổ sung $1$ mà phải $2$ số mới được. Do vậy $\min k=2$, cụ thể như sau:

• Nếu $a^2+b^2+c^2\equiv 0\pmod{3}$ thì bổ sung thêm $d^2\equiv e^2\equiv 0\pmod{3}$.
• Nếu $a^2+b^2+c^2\equiv 1\pmod{3}$ thì bổ sung thêm $d^2\equiv e^2\equiv 1\pmod{3}$.
• Nếu $a^2+b^2+c^2\equiv 2\pmod{3}$ thì bổ sung thêm $d^2-1\equiv e^2\equiv 0\pmod{3}$.

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 22-08-2022 - 15:32

[hxthanh]

Ra là vậy! Cảm ơn em nhé, Phát!
Nhìn vào toàn bộ bài toán thấy khó… mỗi cái đề