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

[HUYVAN]

Cho số nguyên dương $n$. Gọi $S=\{(x, y, z)| x, y, z\in\{0, 1, ..., n}, x+y+z>0}$ là tập gồm $(n+1)^3-1$ điểm trong không gian ba chiều. Xác định số nhỏ nhất các mặt phẳng có thể có, sao cho phần hợp của chúng chứa $S$ nhưng không chứa điểm $(0, 0, 0)$

[ThangTongHop]

bài này ta thử xét 1 mạng lưới vuông nxn, với tọa độ đánh dấu là 0,1,2,...,n
Ta CM cần ít nhất 2n đường thẳng để lấy hết các điểm trong hình vuông nxn nói trên
Ta CM bằng quy nạp
giẩ sử đúng với mọi k<n
ta cm đúng với k=n
Xét 4n-1 điểm ở biên hcn
Nếu ko có đường thẳng nào được chọn là cạnh của HCN
thì mỗi đường đi qua tối đa 2 trong số 4n-1 điểm đang xét từ đó ta có cần ít nhất 2n đường
Nếu có 1 đường được chọn là cạnh của HCN thì nó là đường trên hoặc bên phải
giả sử là đường bên phải
thì ta xét hình vuông (n-1)x(n-1) với 4 đỉnh có tọa độ (0,0), (0,n-1), (n-1,0), (n-1,n-1)
Theo quy nạp cần ít nhất 2n-2 đường thẳng để phủ hêt hình vuông này
Có 2n-2 đỉnh của hình vuông ban đầu chưa bị phủ nằm trong hình vuông mới. Để phủ ngần ấy điểm cần ít nhất n-1 đoạn vì 2 cạnh bên dưới và trái của hình vuông này ko được phép chọn
Còn n-1 đoạn ko đủ phủ n-1 đỉnh cạnh trên hình vuông ban đầu và 2n-3 điểm biên của hình vuông mới chưa bị phủ ( CM phản chứng điều này bằng nhận xét mỗi đoạn trong số n-1 đoạn thoả mãn phải đi qua đúng 1 điểm ở cạnh trên hình vuông ban đầu). Do đó cần thêm 1 đoạn nữa
Vậy theo quy nạp ta cần ít nhất 2n đoạn
Ta có đpcm

Từ đây ta đưa vào ko gian và cũng được số mặt phẳng nhỏ nhất là 2n
cách dựng thỏa mãn thì đơn giản bằng cách tô tất các đường chéo theo chiều " \", hoặc tô n mặt phẳng theo chiều thẳng đứng và n mặt phẳng theo chiều ngang

Bài viết đã được chỉnh sửa nội dung bởi ThangTongHop: 26-07-2007 - 22:27

[tanlsth]

Trong không gian thì kết quả phải là $ 3n $ em ah.Không thể nói áp dụng vào là được đâu

[Alexi Laiho]

Bài này có thể tổng quát cho trường hợp m-dimensional, giải hơi khó hơn 1 tí.

[leoteo]

Có được vinh hạnh nhìn cái marking scheme của bài này. Theo như cái mức điểm ban đầu của BTC thì bài giải như trên của bạn ThangTongHop (gộp cả lời giải đã chỉnh sửa) được... 0 điểm. Nhưng sau BTC nghĩ lại muốn cho mấy bạn biết câu một ít điểm, thì bài như của bạn được lên 1 điểm .

[hungkhtn]

Có được vinh hạnh nhìn cái marking scheme của bài này. Theo như cái mức điểm ban đầu của BTC thì bài giải như trên của bạn ThangTongHop (gộp cả lời giải đã chỉnh sửa) được... 0 điểm. Nhưng sau BTC nghĩ lại muốn cho mấy bạn biết câu một ít điểm, thì bài như của bạn được lên 1 điểm .

Hi hi, sao anh dọa em nó thế Mà anh có tham ra chấm bài này không vậy? h..m có lời giải ko dùng kết quả combinatorial nullstellenstaz à?

[ThangTongHop]

Sr em giải nhầm bài 6, nhờ các anh xem giúp bài 3 em giải thế có được ko

Bài viết đã được chỉnh sửa nội dung bởi ThangTongHop: 30-07-2007 - 00:34

[CXR]

Hi hi, sao anh dọa em nó thế Mà anh có tham ra chấm bài này không vậy? h..m có lời giải ko dùng kết quả combinatorial nullstellenstaz à?

Ngoài cách dùng định lý không điểm rời rạc ra, bài này còn có thể giải đc bằng sai phân (một chú Đức và một chút Italy làm thế) .. cách này rất hay và tự nhiên - mọi người thử nghĩ xem

[BadMan]

Bài này của Hà Lan gửi đến mà thử đối chiếu thì thấy cả 6 thành viên Hà Lan bị zero P6 :-p (nhưng cũng tại đoàn HL kém nữa, có được mỗi cái Đồng)

[tanlsth]

Có lẽ Việt Nam chỉ được cái học thuộc nhiều sách nên mấy cái nài thuộc dạng cũ kia thì ngon ơ nhưng cứ đụng tới mấy bài mới cái là có lẽ lại hay chết.So với nước ngoài thì không ăn thua