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

[CXR]

RongChoi: Về bài toán các quân hậu, phải chăng số lớn nhất các quân hậu không ăn nhau = số nhỏ nhất các quân hậu để phủ kín bàn cờ?

Định nghĩa về distance của RongChoi rất hay. Anh cho rằng distance = 0, nhưng để anh nghĩ thêm xem chứng minh thế nào.

MrMATH: Phương pháp tính số cách sắp xếp các quân hậu được tìm bằng cách xây dựng phức đơn như sau. Xét tập http://dientuvietnam...n/mimetex.cgi?i, cột thứ http://dientuvietnam...n/mimetex.cgi?j của bàn cờ bằng biến http://dientuvietnam...ex.cgi?x_{i,j}. Ta xây dưng phức đơn http://dientuvietnam...etex.cgi?\Delta trên http://dientuvietnam...n/mimetex.cgi?B như sau: http://dientuvietnam...etex.cgi?\Delta nếu khi đặt các quân hậu vào các ô đánh thứ tự http://dientuvietnam...etex.cgi?\Delta thực sự là một phức đơn.
(2) http://dientuvietnam...mimetex.cgi?f_i là số các mặt chiều http://dientuvietnam...mimetex.cgi?i-1 của http://dientuvietnam...tex.cgi?\Delta. Ta cần tìm http://dientuvietnam...imetex.cgi?f_n. Việc tính http://dientuvietnam...mimetex.cgi?f_i được thông qua định lý sau về chuỗi Hilbert-Poincaré của http://dientuvietnam...k[\Delta].

Định lý: Chuỗi Hilbert-Poincaré của vành http://dientuvietnam...?k[\Delta] được tính như sau:


http://dientuvietnam...[\Delta]_i là thành phần bậc http://dientuvietnam...n/mimetex.cgi?i của vành http://dientuvietnam...?k[\Delta] (nghĩa là không gian vector sinh bởi các đa thức bật http://dientuvietnam...n/mimetex.cgi?i không nằm trong http://dientuvietnam...ex.cgi?I_\Delta).

Để tính chuỗi http://dientuvietnam...x.cgi?I_\Delta.

Bài tập: Chứng minh rằng

http://dientuvietnam...tex.cgi?x_{i,j} và http://dientuvietnam...tex.cgi?x_{k,j} ăn được nhau

[RongChoi]

RongChoi: Về bài toán các quân hậu, phải chăng số lớn nhất các quân hậu không ăn nhau = số nhỏ nhất các quân hậu để phủ kín bàn cờ?

Theo em thì số nhỏ nhất các quân hậu để phủ kín bàn cờ luôn nhỏ hơn số quân hậu lớn nhất không ăn nhau. Ví dụ trong trường hợp bàn cờ 8x8 thì số nhỏ nhất các quân hậu có thể phủ kín bàn cờ chỉ là 5.
Thực ra mình có thể dễ chứng minh điều này : Với bàn cờ nxn anh có thể đặt n-2 quân hậu trên đường chéo (trừhai ô ở góc) để phủ kín bàn cờ, trong khi đó số lớn nhất các quân hậu không ăn nhau là n.

Định nghĩa về distance của RongChoi rất hay. Anh cho rằng distance = 0, nhưng để anh nghĩ thêm xem chứng minh thế nào.

Nếu anh chứng minh được distance = 0 thì mình có thể xây dựng được một thuật toán tính chỉ số trải (và chắc chỉ số phủ cũng tương tự) trong thời gian tuyến tính theo
http://dientuvietnam.net/cgi-bin/mimetex.cgi?p mà không cần thông qua các công việc nặng nhọc như tính số chiều của vành đa thức http://dientuvietnam.net/cgi-bin/mimetex.cgi?k[\Delta] nhỉ. Và trong trường hợp đó, mình chắc là có thể chứng minh được thuật toán tính chỉ số trải/phủ đó là tối ưu.

[canh_dieu]

Nếu quả thật distance=0 thì có nghĩa là phức đơn hình http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta là pure. Liệu mình có thể chứng minh được http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_{\Delta} là iđêan căn của một iđêan dấu của một iđêan nguyên tố nào không anh CXR nhỉ .

Vì có một định lý của Sturmfels + (?) (làm mạnh một kết quả của ? + ? em quên béng mất rồi ) nói rằng nếu http://dientuvietnam...n/mimetex.cgi?P là một iđêan nguyên tố bất kỳ, "<" là một thứ tự đơn thức tùy ý thì vành http://dientuvietnam.net/cgi-bin/mimetex.cgi?S/\sqrt{int_<(P)} là equidimensional và connected in dimension one. Mà đối với vành http://dientuvietnam.net/cgi-bin/mimetex.cgi?k&#091;\Delta] thì điều này tương đương với khẳng định rằng phức đơn hình http://dientuvietnam.net/cgi-bin/mimetex.cgi?\Delta là pure và strongly connected.

(Em thấy các phần tử sinh của http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_{\Delta} trong trường hợp chỉ số trải rất đơn giản nên nghĩ loanh qoanh một chút. Khéo khi lại phức tạp hơn chứng minh trực tiếp )

[CXR]

Vì đặc trưng của http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_\Delta khá đơn giản nên anh nghĩ chứng minh trực tiếp chắc dễ hơn là thông qua iđêan dấu .. nhưng mới thử nghĩ một chút thì thấy khó quá .. hehe Để anh nghĩ thêm xem thế nào. canh_dieu thử tìm iđêan nguyên tố P mà http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_\Delta là iđêan dấu xem thế nào.

[canh_dieu]

Hì hì, em thì lại thấy do iđean http://dientuvietnam.net/cgi-bin/mimetex.cgi?I_{\Delta}, có phải là chuyện dễ đâu .

Không chứng minh được thì em đành phải đi tìm phản ví dụ vậy. Hóa ra lại tìm được thật. Mà lại rất đơn giản.

Xét http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{x^2,y^2\}). Tuy nhiên, http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{xy\} cũng là một tập trải tối đại.

Dễ thấy rằng luôn luôn có thể tìm được phản ví dụ kiểu như trên cho trường hợp http://dientuvietnam...mimetex.cgi?n=2 và chẵn.

[CXR]

Đang định hôm nào ngồi nghiêm túc nghĩ xem thế nào .. may mà canh_dieu đã tìm ra phải ví dụ .. đỡ phải mất công

Thế theo xây dựng của canh_dieu thì distance có khả năng rất lớn đấy nhỉ (lớn tùy ý?).