Đến nội dung

Hình ảnh

Tìm số phần tử lớn nhất của tập đặc biệt M.

- - - - -

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

#1
BurakkuYokuro11

BurakkuYokuro11

    Thượng sĩ

  • Thành viên
  • 230 Bài viết

BÀI TẬP CƠ BẢN VỀ PHẦN TỬ CỦA TẬP HỢP HỮU HẠN)

Bài 1 : Tập hợp $M\subset R$ được gọi là tập đặc biệt nếu thoả mãn đồng thời 2 điều kiện :

(i) Với mỗi cặp $x,y\in M$ và $x\neq y$ thì $x+y\neq 0,xy\neq 0$ và có đúng 1 trong 2 số là số hữu tỷ.

(ii) Với mỗi $x\in M$ thì $x^2\in \mathbb{R}\setminus \mathbb{Q}$.

Tìm số phần tử lớn nhất của tập đặc biệt M.

(RMN_MO 2013)

Bài 2 : Cho n là số nguyên dương lớn hơn 1 và S là tập hợp các tập con gồm n phần tử của tập hợp $\left \{1,2,...,2n \right \}$ . Xác định $\underset{A\in S}{max}\left ( \underset{x,y\in A :x\neq y}{min}[x;y] \right )$, ở đây $[x,y]$ là BCNN của x và y.

(RMN_MO 2013)

Bài 3 : Cho tập hợp khác rỗng $S\subset \mathbb{Z}$ thoả mãn :

(i) Tồn tại 2 phần tử $a,b\in S$ : $(a,b)=(a-2,b-2)=1$.

(ii) Nếu $x,y\in S$ thì $x^2-y\in S$ (x,y không nhất thiết phân biệt ).

Chứng minh rằng $S=\mathbb{Z}$

(T9/420 THTT)

Bài 4 : Cho tập hợp khác rỗng $X\subset \mathbb{N}\setminus \left \{ 0 \right \}$ thoả mãn đồng thời 2 điều kiện :

(i) Tồn tại $x,y\in M :(x,y)=1$

(ii) Với mọi phần tử $a,b\in X:a+b\in X$ .

Gọi $T= \mathbb{N}\ast \setminus X$ và $S(T)=\sum_{a\in T}a$ . Chứng minh rằng :

a) T là tập hữu hạn 

b)$\left | T \right |\geq \sqrt{S(T)}$


Bài viết đã được chỉnh sửa nội dung bởi BurakkuYokuro11: 20-08-2018 - 21:47

WangtaX

 


#2
Hr MiSu

Hr MiSu

    Thượng sĩ

  • Thành viên
  • 206 Bài viết

Bài 4 : Cho tập hợp khác rỗng $X\subset \mathbb{N}\setminus \left \{ 0 \right \}$ thoả mãn đồng thời 2 điều kiện :

(i) Tồn tại $x,y\in M :(x,y)=1$

(ii) Với mọi phần tử $a,b\in X:a+b\in X$ .

Gọi $T= \mathbb{N}\ast \setminus X$ và $S(T)=\sum_{a\in T}a$ . Chứng minh rằng :

a) T là tập hữu hạn 

b)$\left | T \right |\geq S(T)$

a) Bổ đề: Định lý sylvester: Cho (a;b)=1 thế thì $N_0=ab-a-b$ là số lớn nhất ko biểu diễn đc dưới dạng $ax+by$, trong đó a,b nguyên dương, x,y nguyên không âm

Capture1894b84210b55dc9.png

Quay lại bài toán: Dễ thấy nếu $x\in T=\mathbb{N}*$ \ $X$ thì $0<x\leq ab-a-b$

Do đó T là hữu hạn


Bài viết đã được chỉnh sửa nội dung bởi Hr MiSu: 20-08-2018 - 21:39

s2_PADY_s2

Hope is a good thing, maybe the best thing, and no good thing ever dies


#3
Hr MiSu

Hr MiSu

    Thượng sĩ

  • Thành viên
  • 206 Bài viết

Bài 4 : Cho tập hợp khác rỗng $X\subset \mathbb{N}\setminus \left \{ 0 \right \}$ thoả mãn đồng thời 2 điều kiện :

(i) Tồn tại $x,y\in M :(x,y)=1$

(ii) Với mọi phần tử $a,b\in X:a+b\in X$ .

Gọi $T= \mathbb{N}\ast \setminus X$ và $S(T)=\sum_{a\in T}a$ . Chứng minh rằng :

a) T là tập hữu hạn 

b)$\left | T \right |\geq S(T)$

Ý b nó cứ sao sao ấy, mỗi phần tử của T đã ko nhỏ hơn 1 rồi, vậy thì tổng của các phần tử chắc chắn phải lớn hơn số phần tử chứ nhỉ


s2_PADY_s2

Hope is a good thing, maybe the best thing, and no good thing ever dies


#4
Hr MiSu

Hr MiSu

    Thượng sĩ

  • Thành viên
  • 206 Bài viết

Bài 2 : Cho n là số nguyên dương lớn hơn 1 và S là tập hợp các tập con gồm n phần tử của tập hợp $\left \{1,2,...,2n \right \}$ . Xác định $\underset{A\in S}{max}\left ( \underset{x,y\in A :x\neq y}{min}[x;y] \right )$, ở đây $[x,y]$ là BCNN của x và y.

(RMN_MO 2013)

Đây là đề RMN_TST 2013, nhìn cái giải khủng quá chả muốn dịch:

https://artofproblem...h621915p3717941


s2_PADY_s2

Hope is a good thing, maybe the best thing, and no good thing ever dies


#5
BurakkuYokuro11

BurakkuYokuro11

    Thượng sĩ

  • Thành viên
  • 230 Bài viết

Ý b nó cứ sao sao ấy, mỗi phần tử của T đã ko nhỏ hơn 1 rồi, vậy thì tổng của các phần tử chắc chắn phải lớn hơn số phần tử chứ nhỉ

Xin lỗi -.- , mình ghi nhầm đề 

Đề đúng : $\left | T \right |\geq \sqrt{S(T)}$

 

Đây là đề RMN_TST 2013, nhìn cái giải khủng quá chả muốn dịch:

https://artofproblem...h621915p3717941

Công nhận là khủng 


WangtaX

 


#6
YoLo

YoLo

    Thượng sĩ

  • Thành viên
  • 223 Bài viết
(RMN_MO 201Bài 3 : Cho tập hợp khác rỗng $S\subset \mathbb{Z}$ thoả mãn :

(i) Tồn tại 2 phần tử $a,b\in S$ : $(a,b)=(a-2,b-2)=1$.

(ii) Nếu $x,y\in S$ thì $x^2-y\in S$ (x,y không nhất thiết phân biệt ).

Chứng minh rằng $S=\mathbb{Z}$

$

Cm $1\in S$

=> $1^{2}-1=0\in S$

=> $0^{2}-1=-1\in S$

=> $1^{2}-(-1)=2\in S$

=> $0^{2}-2=-2\in S$

.......

Làm liên tiếp nhiều lần như vậy tạo ra được tất cả các số vét hết tập $\mathbb{Z}$


Người ta không mắc sai lầm vì dốt mà là vì tưởng là mình giỏi :closedeyes:


#7
Hr MiSu

Hr MiSu

    Thượng sĩ

  • Thành viên
  • 206 Bài viết

Cm $1\in S$

=> $1^{2}-1=0\in S$

=> $0^{2}-1=-1\in S$

=> $1^{2}-(-1)=2\in S$

=> $0^{2}-2=-2\in S$

.......

Làm liên tiếp nhiều lần như vậy tạo ra được tất cả các số vét hết tập $\mathbb{Z}$

Khó nhất là c/m $1\in S$ rồi bạn ơi, lời giải thì có trong THTT 424:

https://drive.google...mRhTTd6Tms/view

>< toàn bài khó


s2_PADY_s2

Hope is a good thing, maybe the best thing, and no good thing ever dies


#8
BurakkuYokuro11

BurakkuYokuro11

    Thượng sĩ

  • Thành viên
  • 230 Bài viết

(BÀI TẬP CƠ BẢN VỀ PHẦN TỬ CỦA TẬP HỢP HỮU HẠN)

 

Bài 2 : Cho n là số nguyên dương lớn hơn 1 và S là tập hợp các tập con gồm n phần tử của tập hợp $\left \{1,2,...,2n \right \}$ . Xác định $\underset{A\in S}{max}\left ( \underset{x,y\in A :x\neq y}{min}[x;y] \right )$, ở đây $[x,y]$ là BCNN của x và y.

(RMN_MO 2013)

 

 

Let $T$ be the set $\{1,2,...,2n\}$ . Call the odd value of an element $t\in T$ to be the largest odd divisor of$t$Note that the odd values are all in the set $\{1,3,...,2n-1\}$ . Let $U=\{1,3,...,2n-1\}$. Take any set $A$ in $S$. Note that since there are $n$ elements in $U$ and $n$ elements in $A$, the odd values of two elements in $A$ must be the same or the set of all odd values of the elements of $A$ must be $U$.

Suppose that there are two elements in $A$ with the same odd value. Let these be $2^{a}c$  and $2^bc$ where $c\in U$ .Thus, since 

$$[2^ac,2^bc]=2^{max(a,b)}c=max(2^ac,2^bc)\le 2n.$$

Thus, the minimum value of the least common multiple of two elements in $A$ is at most $2n$.

Now, suppose that the odd values of $A$ form the whole set $U$. Therefore, for any two elements of $A$ have different odd values. Suppose that 9ad99798ec4c38e165cf517cb9e02b1c9e824103 is an element of $A$ so that $u\le n$. Replacing $u$ by $2u$ will not decrease the minimum value of the least common multiple of two elements in $A$ and this replacement will be valid since $2u\leq 2n$ and 9ad99798ec4c38e165cf517cb9e02b1c9e824103 has a different odd value from the rest of $A$. Thus, the set $A$ for which the minimum such least common multiple will be a maximum is $\{n+1,n+2,...,2n\}$.

Now, since the odd values of the elements of $A$ are all distinct, $A$ can be represented by the set $\{1\cdot 2^{b_1}, 3\cdot 2^{b_3},...,(2n-1)\cdot 2^{b_{2n-1}}\}$ where the $b_i$ are all nonnegative integers. Notice that if $i<j$ are odd integers then $b_i\ge b_j$ since if $b_i<b_j$, then

$$i\cdot 2^{b_i+1}\le i\cdot 2^{b_j}<j\cdot 2^{b_j}\le 2n$$

which is a contradiction.

Suppose that $i< j$ are odd integers such that $i|j$. Since $i|j$ and both are odd, $j\geq 3i$. Therefore,

$$[2^{b_i}\cdot i, 2^{b_j}\cdot j]=2^{max(b_i,b_j)}\cdot [i,j]=2^{b_i}\cdot j\ge 2^{b_i}\cdot 3i=3\cdot (2^{b_i}\cdot i).$$

Now if $i< j$ are odd integers such that $i\not| j$, then there exists an odd prime 36f73fc1312ee0349b3f3a0f3bd9eb5504339011 that divides 34857b3ba74ce5cd8607f3ebd23e9015908ada71 more times than it divides 8122aa89ea6e80784c6513d22787ad86e36ad0cc.Therefore, $[i,j]\ge pj\ge 3j$. Thus,

$$[2^{b_i}\cdot i,2^{b_j}\cdot j]=2^{max(b_i,b_j)}\cdot [i,j]\ge 2^{b_i}\cdot 3j=3\cdot (2^{b_i}\cdot j).$$

Thus, the least common multiple of any two elements of $A$ is at least 2^{b_i})$ where $i\cdot 2^{b_i}\in A$ which is at least $3(n+1)$. Thus, the maximum value that is desired is found by taking $A$ to be the set $\{n+1,n+2,...,2n\}$.

If 174fadd07fd54c9afe288e96558c92e0c1da733a is an odd integer, then note that $n +1$ is even and that $(n+1)/2\le 2n/3$. Let 34857b3ba74ce5cd8607f3ebd23e9015908ada71 be the odd value of $n+1$. Since $(n+1)/2\le 2n/3$, $3i\le 2n$. Therefore, the minimum value of the least common multiple of two elements of $A$ is $3(n+1)$ by taking $i\cdot 2^{b_i}$ and $3i\cdot 2^{b_{3i}}$.

If $n=2$, note that $A=\left \{ 3,4 \right \}$ which means that the value that is desired is $12$.

If $n=4$, then $A=\left \{ 5,6,7,8 \right \}$. Taking the pairwise least common multiples gives that the desired value is 24 by taking 6 and 8.

Now, let 174fadd07fd54c9afe288e96558c92e0c1da733a be an even integer that is at least 6. Note that $n+2$ is an even integer. Let 9ad99798ec4c38e165cf517cb9e02b1c9e824103 be the odd part of $n+2$  and note that $u\le (n+2)/2\le 2n/3$ which implies that $3u\leq 2n$. Thus, $3(n+2)$ is an achievable least common multiple of two elements in $A$. In order to show that this is the least possible achievable value, it suffices to show that $[n+1,i]>3(n+2)$ for all $n+1<i\le 2n$. Let a9f23bf124b6b2b2a993eb313c72e678664ac74a be the odd part of 34857b3ba74ce5cd8607f3ebd23e9015908ada71. If $v\leq n$, then $b_{v}\geq 1$ which implies that

$$[n+1,i]\ge 3(n+1)\cdot 2^{b_v} \ge 6(n+1)\ge 3(n+2).$$

If $v> n$, then $i=v\geq n+1$ which implies that

$$[n+1,i]\ge 3\cdot 2^{b_i}\cdot i\ge 3(n+2).$$

Therefore, if n is even, then $3(n+2)$ is the value desired.

Overall, the answer is $\boxed{3(n+1)}$ if n is odd, $\boxed{3(n+2)}$ if $n\geq 6$ is even, 38693a75a9e00c962455566cda9d06d94da1738b if $n=12$, and c7d2cca89d5aa7ed0a9130ce403b8bf8a23a869c if $n=4$.


Bài viết đã được chỉnh sửa nội dung bởi BurakkuYokuro11: 21-08-2018 - 08:48

WangtaX

 





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

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