Đến nội dung


Hình ảnh

Marathon Tổ hợp và rời rạc VMF

tổ hợp rời rạc marathon

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

#61 halloffame

halloffame

    Sĩ quan

  • Thành viên
  • 431 Bài viết
  • Giới tính:Nam
  • Đến từ:LQĐ
  • Sở thích:Hình học phẳng

Đã gửi 25-09-2016 - 23:19

Từ ô chứa 1 đến ô chứa n^2 có nhiều nhất là n -2 ô. Mà hiệu của 1 và n^2n^2-1 theo Drichlet có 2 ô kề nhau có hiệu 2 lớn bằng n

_Mình nghĩ từ ô chứa $1$ đến ô chứa $n^2$ không phải có nhiều nhất là $n-2$ ô đâu. Ví dụ như bạn điền vào bảng các số theo thứ tự sau:

  Hàng $1: 1,2,...,n.$

  Hàng $2: n+1,n+2,...,2n.$

  $...$

  Hàng $n: n^2-n+1,n^2-n+2,...,n^2.$

  Khi đó ô $1$ và ô $n^2$ sẽ cách nhau $2n-1$ ô bạn ạ.

_Những chỗ mình bôi màu đỏ bạn chịu khó sử dụng Latex để bài viết dễ nhìn hơn nhé.


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 25-09-2016 - 23:19

Sự học như con thuyền ngược dòng nước, không tiến ắt phải lùi.
I am MPCBCNMLHTBHMLPC.


#62 wanderboy

wanderboy

    Binh nhất

  • Thành viên mới
  • 32 Bài viết

Đã gửi 01-11-2016 - 19:06

Bài 17: Cho tập A = {1,2,3...,2016}. Hỏi lấy ra nhiều nhất bao nhiêu phần tử từ tập A để trong những phần tử lấy ra không có phần tử nào bằng tích của hai phần tử còn

Không ai vào làm nhỉ  :(

Xét bài toán với tập 1 đến n:

Xét trường hợp lấy ra tất cả các số lớn hơn hoặc bằng $\sqrt{n}$ , số 1 và số $\left \lfloor \sqrt{n} \right \rfloor$ nếu $\left \lfloor \sqrt{n} \right \rfloor.\left \lfloor \sqrt{n}+1 \right \rfloor > n$ (hiển nhiên thỏa mãn)$a=\left \lfloor \sqrt[4]{n} \right \rfloor$

Giả sử lấy số $a=\left \lfloor \sqrt[4]{n} \right \rfloor$ thì ta có a^3-a  số : (a+1,a^2+a),...,(a^3,a^4) trong đó chỉ 1 trong cặp tồn tại

Ta thấy $a^{3}-a\geqslant 2a^{2}-2$ nên khi chọn a và các số nhỏ hơn ta được dãy ít số hơn dãy đã xét

Giả sử lấy k số $\sqrt[4]{n} \leq  b< \sqrt{n}$ thì tích số min với các số còn lại và tích 2 số lớn nhất ta được k tích khác nhau lớn hơn $\sqrt{n}$ nên ....

Trường hợp k=2 thì tích 2 số và tích số và tích của số nhỏ hơn với số nhỏ nhất lớn hơn căn n sẽ nhỏ hơn n (dễ cm) nên ...

Trường hợp k=1 cmtt

Vậy ta có dãy đã xét là dãy có số phần tử max







Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: tổ hợp rời rạc, marathon

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

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