Road to IMO 2017 to Infinity

[Thgx0312555]

ผมทำวิธีเดียวกันนิแหละ แต่ถ้าทำแบบนี้มันจะติดปัญหาตรงนี้

ข้อความเดิมเขียนโดยคุณ Pitchayut

วิธีผมเอง ไม่รู้มีใครทำแบบนี้ป่าว

ให้ $s_1,s_2,s_3,...,s_{ab+1}$

สมมติขัดแย้งว่า ทุกๆลำดับย่อยเพิ่มแท้ มีความยาวไม่เกิน $a$ และ ทุกๆลำดับย่อยลดแท้ มีความยาวไม่เกิน $b$

จะทาสีตัวเลขทุกตัว โดยให้ $f(n)$ แทนสีของ $s_n$ โดยทาสีตามขั้นตอนต่อไปนี้

1. ทาสี $s_1$ ด้วยสีที่ 1 จากนั้นหาตัวแรกที่น้อยกว่า $s_1$ ให้เป็นตัวที่ $t_{1,2}$)

2. ทำนองเดียวกัน หาตัวแรกที่น้อยกว่า $s_{t_{1,2}}$ ให้เป็นตัวที่ $t_{1,3}$ จากนั้นทำไปเรื่อยๆจนจบลำดับ

3. ทาสี $s_{t_{1,k}}$ ด้วยสีที่ 1 ทุกๆ $k$

4. ดำเนินการเช่นนี้ไปเรื่อยๆ โดยเริ่มจากตัวแรกที่ไม่ถูกทาสี และให้สีเป็น $2,3,4,...$ ไปเรื่อยๆ

สังเกตว่าจะมีช่องที่ทาสีที่ $i$ อยู่ไม่เกิน $b$ ช่อง (เพราะมิฉะนั้นจะเกิดลำดับลดความยาว $b+1$)

และมีสีไม่เกิน $a$ สี เพราะตัวแรกที่ทาสีที่ $i$ สำหรับ $i=1,2,3,...$ จะทำให้เกิดลำดับเพิ่ม

เพราะฉะนั้น จำนวนพจน์ต้องมีไม่เกิน $ab$ พจน์ ซึ่งเป็นข้อขัดแย้ง

จริงเหรอครับ

ปล. ข้อนี้มี alternate solution ที่สวยจริงๆ อยู่ในลิงค์ wiki ที่แปะลิงค์ไปแล้ว

[Beatmania]

จริงๆ ผมชอบ NT สุด จะไม่ปล่อย NT มันก็กระไรอยู่ 555

1.) ให้ $k,n$ เป็นจำนวนนับโดยที่

$$\underbrace{\phi(\phi(...\phi(}_{k} n)...)=1$$

จงแสดงว่า $n\leq 3^k$ (USATSTST 2016 #4)

2.) ให้ $\sqrt{3}=1.b_1b_2..._{(2)}$ เป็นการเขียน $\sqrt{3}$ ในรูปเลขฐานสอง

จงแสดงว่าสำหรับทุกจำนวนนับ $n$ มีอย่างน้อยหนึ่งจำนวนใน $b_n,b_{n+1},...,b_{2n}$ ที่มีค่าเป็น $1$

(USATST2016 #4)

3.) ให้ $a,b$ เป็นจำนวนนับโดยที่ $a!+b!|a!b!$ จงแสดงว่า $3a\geq 2b+2$ (ISL 2015 N2)

4.) สำหรับจำนวนนับ $n$ เรานิยามให้ $D_n=\left\{d-\frac{n}{d}:d|n,d<\sqrt{n}\right\} $

จงแสดงว่ามีจำนวนนับ $n_1,n_2,...,n_{2016}$ ที่ทำให้

$$|D_{n_1}\cap D_{n_2}\cap ...\cap D_{n_{2016}}|>1$$

(Modified from China MO 2015 #2)

5.) จงหาพหุนาม $P(x)\in\mathbb{Z}[x]$ ทั้งหมดที่มีสมบัติว่ามีจำนวนเต็ม $n$ เป็นอนันต์ที่ $P(n+P(n))$ เป็นจำนวนเฉพาะ

(Canada MO 2016 #3)

ที่ผมลงไปมี 30 ข้อ ทำได้ซัก 15+ ข้อก็คงจะได้ สสวท. 2 ไม่ยากแล้วครับๆ

[Pitchayut]

FE ข้อ 1,3 ได้แล้ว (ขอไม่ลง sol เพราะเหมือนกับ sol ตามท้องตลาด)

NT ข้อ 5 ลองแสดงดูก่อนว่า $P(n)\mid P(n+P(n))$ ที่เหลือก็แค่ไล่ไปเรื่อยๆ

[Lspeed]

พี่ๆครับ พอจะมีโจทย์แนวinvarian,monovarianที่น่าสนใจบ้างไหมครับ?

[Pitchayut]

NT ข้อ 3 unseen แต่ง่ายดีครับ ใช้ความรู้ไม่เกินค่าย 1

สำหรับคนที่อยากฝึก Lifting The Exponent Lemma

1. จงพิสูจน์ว่าไม่มี $(b,m,n)\in\mathbb{N}^3$ ที่ทำให้ $b> 1$ และ $b^m-1$ กับ $b^n-1$ มีเซตของตัวประกอบเฉพาะเป็นเซตเดียวกัน

2. จงหา $(a,m,n)\in\mathbb{N}^3$ ทั้งหมดที่ทำให้ $a^m+1\mid (a+1)^n$

อยากได้ Hint ข้อไหนบอกได้นะครับ

[Thgx0312555]

Hint NT3

hint

$a<b \rightarrow 1+\frac{b!}{a!} \mid \frac{a!}{(b-a)!}$

[Pitchayut]

ผมก็ทำประมาณนั้นแหละครับคุณ Thgx

แล้วก็โจทย์ LTE 2 ข้อ ที่ให้ไปพยายามอย่าใช้ Zsigmondy นะครับ

[Beatmania]

ผมใจดีแจก Hint ให้สำหรับโจทย์ชุดของผมนะครับ

Geometry

G1

ลองลาก $TD$ ไปตัด $\Omega$ อีกรอบและให้ $X$ เป็นจุดสัมผัสของ $\Gamma_a$ กับ $BC$ จะเห็นรูปที่คล้ายๆกัน

G2

มีสองวิธีครับ

Sol1

สร้าง Incircle พิจารณา Composition of Homothety

Sol2

ลองแสดงว่า $AT_A$ เป็น isogonal ของจุดที่ลากเชื่อมจุดสัมผัส A-excenter กับด้าน BC โดยการใช้ Inversion หรืออาจจะใช้รูปข้อก่อนหน้าก็ได้ครับๆ

G3

ตัดกันจุดเดียวอย่างนี้แนะนำ Ceva และ Trig Ceva ครับ

G4

สร้าง B-excenter,C-excenter ลองแสดงว่า $I_b,M,I,N,I_c$ cyclic

G5

ใช้ Lemma เต็มไปหมด

Lemma1

ต่อ $AQ$ ไปตัด $BC$ ที่ $D'$ จะได้ว่า $MD=MD'$

Lemma2

ให้ $N$ เป็น Midpoint $AB$ เราจะได้ว่า $MN,IC,EF$ concurrent

ว่างแล้วเดี๋ยวมาพิมพ์ต่อครับ

[Lspeed]

ข้อความเดิมเขียนโดยคุณ Pitchayut

สำหรับคนที่อยากฝึก Lifting The Exponent Lemma

1. จงพิสูจน์ว่าไม่มี $(b,m,n)\in\mathbb{N}^3$ ที่ทำให้ $b> 1$ และ $b^m-1$ กับ $b^n-1$ มีเซตของตัวประกอบเฉพาะเป็นเซตเดียวกัน

แก้ไม่ออกครับยอม

แต่ว่าผมงงอย่างนึง $(3,1,2)$ มันได้ $3^1-1 = 2$ และ $3^2-1 = 8$ ซึ่งเซตตปก.เฉพาะคือ $\left\{\,\right. 2\left.\,\right\}$ ทั้งคู่หนิครับ ผมเข้าใจโจทย์ผิดไปตรงไหนเปล่าครับ

[Beatmania]

ข้อความเดิมเขียนโดยคุณ Lspeed

แก้ไม่ออกครับยอม

แต่ว่าผมงงอย่างนึง $(3,1,2)$ มันได้ $3^1-1 = 2$ และ $3^2-1 = 8$ ซึ่งเซตตปก.เฉพาะคือ $\left\{\,\right. 2\left.\,\right\}$ ทั้งคู่หนิครับ ผมเข้าใจโจทย์ผิดไปตรงไหนเปล่าครับ

คุณ Lspeed ถูกแล้วครับ จริงๆ ต้องมีเงื่อนไขที่ว่า $b+1$ ไม่เป็นกำลังของสองด้วยครับ

ปล. ไม่มีใครทำเรขาของผมจริงๆ เหรอครับ T_T ผมว่าประมาณนี้เหมาะสำหรับ สสวท ค่าย 1 เลยนะครับๆ

[BAWHK]

G1 ของ Beatmania
ให้ X เป็นจุดสัมผัสของ Excirle A กับ BC
ลาก TD ตัด Circumcircle ABC ที่ K
ไล่มุมเเล้วจะได้ BC||KA
จะได้KACB เป็นสีเหลี่ยมคางหมูหน้าจั่ว
เนื่องจากBX=DC เห็นได้ชัดว่า สามเหลี่ยมBAX เเละ สามเหลี่ยมCKD เท่ากันทุกประการ
เเละ มุมCAT=มุมCKT ดังนั้น มุมBAX=มุมCAT
ลาก AT ตัด Excirle A ที่ S'
จากความสมมาตรเมื่อสะท้อน AS' ข้าม AF จะได้ X เเละ S' ทับกันสนิท
จะได้ 180-มุมAXE=180-AS'E -> มุมAXB = มุมES'T__(1)
จาก สามเหลี่ยมBAX เเละ สามเหลี่ยมCKD เท่ากันทุกประการ
จะได้ มุมAXB=มุมKDC=มุมEDT ดังนั้น มุมEFT=180-มุมEDT=180-มุมAXB__(2)
จาก(1)เเละ(2)จะได้E,S',T,F Concyclic ดังนั้น S=S'
เขียนไม่ค่อยละเอียดเท่าไหร่นะครับช่วยตรวจสอบความถูกต้องให้หน่อยครับ

[Beatmania]

วิธีน้อง BAWHK ถูกแล้วครับผม

จริงๆ สามารถแสดงต่อได้อีกว่า $T$ คือจุดสัมผัสของ A-mixtillinear กับวงกลมใหญ่อีกด้วย

แจก Hint ต่อครับ

Combinatorics

C1

หาอะไรมา"ครอบ" จะจัดการได้ง่ายกว่าครับ

C2

แน่นอนว่าต้องระบายสี มโนกันหน่อย

C3

$1201$ เกี่ยวอะไรกับ $100$ ลองเลขน้อยๆ ก่อนดีมั้ย ??

C4

แสดงว่ามีจำนวนเต็มที่ทำให้ค่าของ $ax+b$ น้อยกว่า gap ของทั้งสองข้างอสมการก่อนครับ

C5

ปกติครับ ไม่น่าจะต้อง Hint :P แต่ตอนสร้างลำบากหน่อย ก็เลยไว้ข้อ 5 ครับ 555

ว่างแล้วเดี๋ยวมาพิมพ์ต่อครับ

[Pitchayut]

สำหรับคนอยากฝึก double counting

1. พิจารณากลุ่มของคน $n$ คน ใดๆ กำหนดให้ $a$ รู้จักกับ $b$ ก็ต่อเมื่อ $b$ รู้จักกับ $a$ ให้ $S=\{\{a,b\}\mid a\ รู้จักกับ\ b\}$ ถ้า $$|S|> \dfrac{n}{4}(1+\sqrt{4n-3})$$ จงพิสูจน์ว่า มี $a,b,c,d$ ในกลุ่มนี้ ที่ทำให้ $a$ รู้จัก $b$, $b$ รู้จัก $c$, $c$ รู้จัก $d$ และ $d$ รู้จัก $a$ (APMO 1989)

2. ให้ $N\in\mathbb{N}$ และให้ $S$ เป็นระบบส่วนตกค้างบริบูรณ์ $\pmod {N^2}$

ให้ $A\subset S$ ที่ $|A|=N$ จงพิสูจน์ว่ามี $B\subset S$ ที่ทำให้

(i) $|B|=N$

(ii) ถ้า $A+B=\{a+b\mid a\in A, b\in B\}$ แล้ว $|A+B|\ge 0.6N^2$ (ยากกว่า IMO SL 1999 C4)

3. พิจารณาจุด $n$ จุดใดๆ ในกระดาษ A4 ที่เมื่อลากเชื่อม 2 จุดใดๆ เส้นที่ได้จะต้องไม่ขนานกับด้านทั้ง 4 ของกระดาษ และไม่มีจุดใดๆ อยู่ตรงมุมหรือขอบกระดาษ

จงพิสูจน์ว่าถ้าเราตัดกระดาษเป็นรูปสี่เหลี่ยมผืนผ้าหลายๆ ชิ้น โดยที่จุดทุกจุดจะต้องเป็นมุมหรือขอบของกระดาษที่ถูกตัด แล้วเราจะต้องตัดกระดาษออกเป็นอย่างน้อย $n+1$ ชิ้น

(IMO SL 2014 C1)

4. ในกลุ่มคนที่มี $2n+1$ คน ซึ่งมีสมบัติว่า ทุกๆ เซต $S$ ของคน $n$ คน จะมีอย่างน้อย $1$ คนนอก $S$ แต่เป็นเพื่อนกับทุกคนใน $S$

จงพิสูจน์ว่ามีอย่างน้อย $1$ คน ที่เป็นเพื่อนกับทุกๆ คนใน $S$

[BAWHK]

ให้ $m,n$ เป็นจำนวนนับโดยที่ $\phi(5^m-1)=5^n-1$ จงแสดงว่า $gcd(m,n)>1$
สมมติ $gcd(m,n)=1$
ให้$p_i$ เป็นจำนวนเฉพาะคี่ที่เเตกต่างกัน เเละ $a_0,a_i$ เป็นจำนวนเต็มบวก สำหรับ $i=1,2,...,k$
ซึ่ง $5^m-1=2^{a_0}p^{a_1}_1...p^{a_k}_k$
จะได้
$5^n-1=\phi(5^m-1)=2^{a_0-1}(p^{a_1}_1-p^{a_1-1}_1)..(p^{a_k}_k-p^{a_k-1}_k)$
เเต่ $gcd(5^m-1,5^n-1)=4$
ทำให้ $a_0=2,a_1=..=a_k=1$ นั่นคือ
$5^m-1=4p_1...p_k$ เเละ $5^n-1=2(p_1-1)...(p_k-1)$
ถ้า m เป็นจำนวนคู่ จะทำให้ $8\mid 5^m-1$ เเต่ $8\nmid 4p_1...p_k$ ขัดเเย้งดังนั้น $m$ เป็นจำนวนคี่
$5^{m+1} \equiv 5 \pmod{p_j}$ ทุก $0<j<k+1$ $\Rightarrow$ $\left(\frac{5}{p_j}\right)=1$ เเละจาก $\left(\frac{5}{p_j}\right) \cdot \left(\frac{p_j}{5}\right) = (-1)^{\frac{5-1}{2}\cdot \frac{p_j-1}{2}}=1$
ดังนั้น $\left(\frac{p_j}{5}\right)=1$ นั่นคือ $p_j \equiv 1,4 \pmod{5} $
ถ้า $p_j \equiv 1 \pmod{5}$ จะทำให้$ 5\mid 5^n-1$ ขัดเเย้ง
ดังนั้น$ p_j \equiv 4 \pmod{5}$ เท่านั้น
ดังนั้น $5^m-1 \equiv 4^{k+1} \pmod{5} \Rightarrow -1 \equiv 4^{k+1} \pmod{5}$ (จะได้ $k$ เป็นจำนวนคู่เท่านั้น) เเละ
$5^n-1 \equiv 2(3^k) \pmod{5} \Rightarrow -1 \equiv 2(3^k) \pmod{5}$
จากทั้ง$2$ จะได้ $3^k \equiv 2(-1)^k \pmod{5} \Rightarrow (-1)^L \equiv 2 \pmod{5}$ เมื่อ $k=2L$ ขัดเเย้ง
ดังนั้น$ gcd(m,n)>1$

[ThE-dArK-lOrD]

ข้อความเดิมเขียนโดยคุณ Pitchayut

4. ในกลุ่มคนที่มี $2n+1$ คน ซึ่งมีสมบัติว่า ทุกๆ เซต $S$ ของคน $n$ คน จะมีอย่างน้อย $1$ คนนอก $S$ แต่เป็นเพื่อนกับทุกคนใน $S$

จงพิสูจน์ว่ามีอย่างน้อย $1$ คน ที่เป็นเพื่อนกับทุกๆ คนใน $S$

Russia 2001