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

[QUANVU]

Cho số nguyên n>2. Mỗi cạnh và mỗi đường chéo của một n-giác đều đã được đánh số bởi 1 trong các số 1,2,...,r theo một cách sao cho các điều kiện sau được thỏa mãn đồng thời:
a)Mỗi số trong 1,2,...,r được dùng ít nhất một lần.
b)Trong mỗi tam giác có 3 đỉnh là các đỉnh của n-giác đều, hai cạnh được viết cùng một số và số này lớn hơn số được viết ở cạnh thứ ba.

Tìm giá trị lớn nhất của r sao cho điều này là có thể. Với giá trị r đó, có bao nhiêu cách đánh số thỏa mãn?

[manutd]

Nếu đề bài yêu cầu tìm Min n thì lời giải hoàn toàn tương tự Bài 3 VietNam TST 2006, $n=\lfloor \log_2n\rfloor +1$.
Ở đây lại là tìm Max n. Vậy có nghĩa là n không chỉ có min mà còn cả max nữa. Một đánh giá còn chặt hơn.

[novatena]

Bài này là IMO shortlisted 2005. Max $r$ là $n-1. $

[duyenmit]

lời giải như thế nào vậy hả bạn novatena

[tanlsth]

Nếu như là $ max $ thì khá đơn giản
Ta có thể chứng minh bằng qui nạp $ r=n-1 $
Kết quả câu $ b $ bằng $ \dfrac{n!(n-1)!}{2^{n-1}} $

[HUYVAN]

Nếu như là $ max $ thì khá đơn giản
Ta có thể chứng minh bằng qui nạp $ r=n-1 $

Chắc anh Tân quá bận nên không thể post lên lời giải hoàn chỉnh, bạn nào post hộ cái nhé!

[manutd]

Okie, MU sẽ post lời giải trong thời gian sớm nhất (nếu không ai post sớm hơn )

[vnm]

nếu chỉ xét các cạnh đánh số r thì nó sẽ chia tập các đỉnh của đồ thị ra 2 tập A và B mà 2 đỉnh nối vơi nhau khi và chỉ khi nó thuộc 2 tập khác nhau.Mỗi tập đỉnh này đánh số bởi r_A và r_B số và thỏa mãn điều kiện đề bài->$r_A\leq\ |A|-1$...
như vậy theo quy nạp $r\leq\ (|A|-1)+(|B|-1)+1=n-1$
câu b dùng truy hồi;mỗi cách đánh số được xác định duy nhất bởi tập A có k phần tử-$C_{n}^{k}$;mỗi tập có $a_k$ cách đánh số;tập B có n-k phần tử ->$a_{n-k}$ cách đánh số
->$a_n=\sum C_{n}^{k}a_ka_{n-k}$
sau đó chứng minh quy nạp a_n có dạng trên