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

[K09]

cho M={1,2,3,....,3n}.Phân hoạch M thành A,B,C có n phần tử .CMR có thể chọn từ mỗi tập 1 số sao cho số này bằng tổng 2 số kia
KCT

[anhminh]

Bài tổng quát :
cho M={1,2,3,....,3n}. Phân hoạch M thành A,B,C có sao cho mỗi tập đều có lớn hơn n/4 phần tử .
CMR có thể chọn từ mỗi tập 1 số sao cho số này bằng tổng 2 số kia

http://www.mathlinks...opic.php?t=3781

Suppose for a contradiction that it is possible to color each of the integers 1,2,...,n by one of the three colors, say red, blue, green, such that there is no tricolor solution of the equation x+y = z, and such that each of the color is used at least n/4 times.

Wlog, we may assume that 1 is red. Thus, there do not exist two consecutive integers which are blue and green.
In the following, the interval [a,b]denotes {a,a+1,...,b}. Note that |[a,b]| = b-a+1.
From above the blue and green integers form some disjoint monochromatic intervals, with at least a red integer as a separator.

- First, we prove that if there is a green (resp. blue) interval A such that |A| > 1 then there is no blue (resp. green) interval B such that |B| > 1 :
Since there is a finite number of interval, we may consider the green interval A = [a_1, a_2] with maximal length among the green intervals, and a blue interval B = [b_1, b_2] with maximal length among the blue intervals.
Then, for a in A and b in B, |a-b| is not red, since we have no tricolor solution to x+y = z.
Let C = {|a-b| / a in A and b in B}. Then, C is not empty and contained in {1,2,...,n}. Moreover, it contains no red element thus, from above, it is a monochromatic interval. More precisely :
C = [b_1 - a_2, b_2 - a_1] if a_2 < b_1
C = [a_1 - b_2, a_2 - b_1] if b_2 < a_1.
Then, in both cases |C| = |A| + |B| - 1. Then, if |A|, |B|  \geq 2, then |C| > |A| and |C| > |B|, which contradicts the maximality of A and B.

Wlog, we then assume that there is no green interval A such that |A| > 1, that is there do not exist two consecutive green integers.

- Then, we prove that there exist two consecutive blue integers :
If not, since blue and green integers are never consecutive ones, and since 1 is red, it would follow that for each blue integer b, the number b-1 is red. Similarly, for each green integer g, we would have g-1 red. Thus, there would be at least n/2 red integers, which contradicts that the are more than n/2 non-red integers.

- Now, we prove that there exist g and g+2 which both are green :
First, note that, from above, if g  \leq n-1 is green, then g  \geq 2 and g-1 and g+1 are red.
Suppose, for a contradiction, that there is no green integer g such that g+2 is green too. Let N®, N(G), N(B) be the number of red, green, blue integers respectively.
When g runs over the set of the green intgers with g \leq  n-1, the intervals [g-1, g+1] form a family of pairwise disjoints intervals, each containing 2 red integers. Thus :
- If n is not green, then N®  \geq  2N(G), from which we deduce that
n = N® + N(G) + N(B)  \geq 3N(G) + N(B) > 3n/4 + n/4 = n, a contradiction.
- If n is green, then N®  \geq  2N(G) - 1 and 2 is green (if not 1 has not been counted and we have the same contradiction as above). If B is the blu interval with maximal length, with the above notations, then b_2 < n. Thus b_2 + 1 is red. Moreover, since |B|  \geq  2, it follows that b_2 - 1 is blue. Thus (b_2 - 1) + 2 = b_2 + 1 is a tricolor solution of x+y = z. A contradiction again, hence result.

Now, let's suppose that g and g+2 are geen.
Then g+1 is red and, if B is the same as above, we either have b_1 > g + 2 or b_2 < g.
- If b_1 > g + 2 : Let E = {b-g / b in B} \cup  {b-g-2 / b in B}. We will prove that E is a monochromatic interval :
Let x be in E. If x = b-g, then x+g = b, where g is green, b is blue. If x = b-g-2, then x + (g+2) = b, where g+2 is green and b is blue. In both cases, we deduce that x is not red.
From B = [b_1, b_2], we deduce that E = [b_1 - g, b_2 - g]  \cup  [b_1 - g - 2, b_2 - g - 2]. And, since b_1 < b_2, we have b_2 - g - 2  \geq  b_1 - g - 1, thus E is an interval.
Then E is an interval which contaions no red integer. From above, we deduce that E is monochromatic, but not red.
Moreover |E| = b_2 - g - (b_1 - g - 2) + 1 = |B| + 2. Thus, from the maximality of B, we deduce that E is not blue. And, since |B| > 2, it follows that E is not green. A contradiction.

- If b_2 < g, we use the same reasoning on E' = {g-b / b in B} \cup  {g+2-b / b in B}, to obtain the same contradiction.

And we are done....

Note that the result is optimal in the sense that for n= 4k, we may color the odd integers in red, the numbers of the form 4p+2 in blue and the numbers of the form 4p in green. Then N®, N(B), N(G)  \geq  4 and, by parity argument, there is no tricolor solution of x+y = z.

[anhminh]

Lời giải cho cả 2 bài đây! (tiếng Việt)

File gửi kèm

•  Indian_TST_2003_and_its_generalization.pdf   170.63K   180 Số lần tải