Đến nội dung

Hình ảnh

GIẢI ĐẤU VÒNG TRÒN $2N+1$ ĐỘI

- - - - -

  • Please log in to reply
Chủ đề này có 8 trả lời

#1
supermember

supermember

    Đại úy

  • Hiệp sỹ
  • 1644 Bài viết

Bài toán: Một cuộc đấu vòng tròn gồm $2n+1$ đội trong đó $2$ đội bất kỳ gặp nhau đúng $1$ lần. $3$ đội $X; Y; Z$ được gọi là 1 bộ ba "khó đoán" nếu $ X$ thắng $Y$, $Y$ thắng $Z$ và $Z$ thắng $X$. Biết rằng giải dấu không có trận hòa nào. Hãy tính:

 

a. Số bộ ba "khó đoán" ít nhất có thể có

b. Số bộ ba "khó đoán " nhiều nhất có thể có


Bài viết đã được chỉnh sửa nội dung bởi supermember: 04-09-2021 - 12:28

Khi bạn là người yêu Toán, hãy chấp nhận rằng bạn sẽ buồn nhiều hơn vui :)

#2
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4990 Bài viết

Ít nhất có thể có thì chắc chắn là "0" :D Và không nhất thiết phải $2n+1$. Với bất kỳ $N$ nào thì cũng tồn tại một trường hợp không có bộ 3 "khó đoán".

Đánh số các đội theo số thứ tự từ $1$ đến $N$. Xét trường hợp đội $j$ thắng đội $i$ nếu $j > i$. Như vậy với bất kỳ bộ 3 $(i,j,k)$ nào, giả sử $i<j<k$ thì mặc dù $k$ thắng $j$, $j$ thắng $i$, nhưng $i$ lại thua $k$. Do đó số bộ ba "khó đoán" ít nhất là 0.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#3
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4990 Bài viết

Còn trường hợp GTLN thì em chưa có nhiều ý tưởng, chỉ mới có ý này. Em ghi lại để khỏi quên :)

Từ cách xây cấu hình cực tiểu, ta có thể chứng minh là trong trường hợp cấu hình cực đại, sẽ không có đội nào "bất bại" (thắng mọi đội còn lại).

Thật vậy, giả sử một đội $i$ thắng hết $N-1$ đội còn lại. Ta chọn 2 đội $j,k$ trong $N-1$ đội (khác $i$) và $j$ thắng $k$.

Dễ thấy là không tồn tại một đội $l$ nào khác $i,j,k$ để $(i,k,l)$ tạo thành một bộ 3 "khó đoán" (vì $i$ thắng cả $k$ và $l$). Do đó, nếu xét một cấu hình y như hiện tại, khác ở chỗ là $k$ thắng $i$, thì số bộ 3 "khó đoán" sẽ không giảm đi (vì không có bộ 3 nào mất đi) mà lại tăng lên ít nhất là 1 (cụ thể là $(i,j,k)$): phi lý với giả thiết cấu hình cực đại ban đầu.

Vì thế, cấu hình cực đại sẽ không chứa đội nào "bất bại".

Tương tự, cấu hình cực đại cũng sẽ không chứa đội nào "toàn thua".


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#4
supermember

supermember

    Đại úy

  • Hiệp sỹ
  • 1644 Bài viết

Giải ra câu a là cũng giỏi rồi.

 

Số bộ ba khó đoán nhiều nhất có thể có là $ \frac{n(n+1)(2n+1)}{6}$, khúc xây dựng hơi khó :)

Và trong cách xây dựng thì mỗi đội cũng sẽ có số ván thắng và thua bằng nhau và bằng $n$.


Bài viết đã được chỉnh sửa nội dung bởi supermember: 05-09-2021 - 23:42

Khi bạn là người yêu Toán, hãy chấp nhận rằng bạn sẽ buồn nhiều hơn vui :)

#5
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4990 Bài viết

Giải ra câu a là cũng giỏi rồi.

 

Số bộ ba khó đoán nhiều nhất có thể có là $ \frac{n(n+1)(2n+1)}{6}$, khúc xây dựng hơi khó :)

Và trong cách xây dựng thì mỗi đội cũng sẽ có số ván thắng và thua bằng nhau và bằng $n$.

Nhìn đáp án giống tổng các bình phương từ $1$ đến $n$ anh nhỉ :) Em đang nghĩ theo hướng quy nạp: lấy cấu hình cực đại của $2n+1$, sau đó nhét thêm 2 đội $2n+2, 2n+3$ vào và giả sử $2n+3$ thắng $2n+2$. Giờ cho $2n+1$ đội ban đầu thắng $2n+3$, trong khi $2n+2$ thắng các đội đó. Như vậy là tạo thêm ít nhất $2n+1$ bộ 3 khó đoán. Cơ mà có vẻ vẫn còn thiếu kha khá :(

 

Nếu đổi góc nhìn sang đồ thị thì bài toán sẽ quy về tìm số lượng tối đa của chu trình độ dài $3$ trong một đồ thị có hướng toàn phần (directed complete graph).


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#6
DOTOANNANG

DOTOANNANG

    Đại úy

  • ĐHV Toán Cao cấp
  • 1609 Bài viết
Cho em kéo topic về Box của Toán Đại cương được k anh ?? Mà hiện tại em cũng k có quyền hạn này nữa.

#7
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4990 Bài viết

Cho em kéo topic về Box của Toán Đại cương được k anh ?? Mà hiện tại em cũng k có quyền hạn này nữa.

Anh thấy để đây hợp lý mà em?


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#8
DOTOANNANG

DOTOANNANG

    Đại úy

  • ĐHV Toán Cao cấp
  • 1609 Bài viết

Anh thấy để đây hợp lý mà em?

Tại nó liên quan tới Lí thuyết Đồ thị nữa. Với lại mảng Toán Rời rạc của bên em nó trống trơn luôn.

#9
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4990 Bài viết

Tại nó liên quan tới Lí thuyết Đồ thị nữa. Với lại mảng Toán Rời rạc của bên em nó trống trơn luôn.

Anh thấy cái đồ thị chỉ là một biểu diễn khác, với anh cũng không biết giải thế nào :D Để đây cho các bạn nhỏ thảo luận cũng không sao đâu :)


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh