Đến nội dung


Chú ý

Diễn đàn vừa được bảo trì và nâng cấp nên có thể sẽ hoạt động không ổn định. Các bạn vui lòng thông báo lỗi cho BQT tại chủ đề này.


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

  • Điều hành viên OLYMPIC
  • 436 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

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

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