#1
|
||||
|
||||
Putnam 2016
ข้างล่างนี้เป็นการแข่งขัน Putnam ที่ผ่านไปอาทิตย์ที่แล้ว ลองทำดูครับ
|
#2
|
|||
|
|||
เอาข้อทีผมทำได้ไปก่อนละกัน 555
สังเกตว่า $\dfrac{d^j}{dx^j}x^n=n(n-1)(n-2)...(n-j+1)x^{n-j}$ เพราะฉะนั้น $j=8$ สอดคล้อง เนื่องจาก $2016\mid 8!$ และ $8!\mid n(n-1)...(n-7)$ ส่วนการแสดงว่า $j\le 7$ ไม่ได้ ให้เลือก $p(x)=x^8$ จำนวน squarish สามารถเขียนได้แบบเดียวในรูป $x^2+y^2$ เมื่อ $y^2\le 2x$ เพราะฉะนั้น $$S(N)=\sum_{x^2+y^2\le n, y^2\le 2x}1=\sum_{x\le\sqrt{N}}\sum_{y^2\le\min\{N-x^2,2x\}}1$$ สังเกตว่า $0<\sqrt{N+1}-\sqrt{N}\le 1$ เพราะฉะนั้นมีจำนวนเต็มอย่างมากจำนวนเดียวในช่วง $(\sqrt{N+1}-1,\sqrt{N})$ ซึ่งเมื่อ $x$ เท่ากับจำนวนนั้น จะส่งผลต่อผลบวกไม่เกิน $N-(\sqrt{N+1}-1)^2=2(\sqrt{N+1}-1)=O(\sqrt{N})$ สังเกตว่า $x\le\sqrt{N+1}-1\Leftrightarrow N-x^2\ge 2x$ เพราะฉะนั้น $$\left(S(N)=\sum_{x_\le\sqrt{N}}\sum_{y^2\le 2x}1\right)+O(\sqrt{N})=\sum_{x\le\sqrt{N}}(\sqrt{2x}+O(1))+O(\sqrt{N})=\sum_{x\le\sqrt{N}}\sqrt{2x}+O(\sqrt{N})$$ ผลบวกด้านซ้ายสามารถประมาณได้โดยใช้ Partial Summation Formula $$\sum_{x\le\sqrt{N}}\sqrt{2x}=\sqrt{N}\sqrt{2\sqrt{N}}-\int_{1}^{\sqrt{N}}\lfloor x\rfloor\dfrac{1}{\sqrt{2x}}dx=\sqrt{2}N^{0.75}-\int_{1}^{\sqrt{N}}\dfrac{x}{\sqrt{2x}}+\int_{1}^{\sqrt{N}}\dfrac{\{x\}}{\sqrt{2x}}$$ Integral ซ้าย สามารถคำนวณได้โดยตรงเป็น $\dfrac{\sqrt{2}}{3}N^{0.75}+O(1)$ และอินทิกรัลขวาคือ $O(\sqrt{N})$ เพราะฉะนั้น เราได้สูตร $S(N)=\dfrac{2\sqrt{2}}{3}N^{0.75}+O(\sqrt{N})$ ซึ่งให้คำตอบที่ต้องการ : โจทย์คลาสสิกครับ เลือก $3$ จุด $D,E,F$ ที่ form ตัวเป็นรูปสามเหลี่ยมที่มีพื้นที่มากที่สุด จากนั้นให้ $\Delta PQR$ เป็นรูปสามเหลี่ยมที่มี $D,E,F$ เป็นจุดกึ่งกลางด้าน สมมติว่ามีจุด $T$ ที่อยู่นอก $\Delta PQR$ จะพบว่าเกิดสามเหลี่ยมใหม่ที่มีพื้นที่มากกว่า (ลองวาดรูปประกอบดู) ซึ่งเกิดข้อขัดแย้ง ลาก $PS$ ตั้งฉาก $QR$ ที่ $S$ แล้วให้ $P'$ เป็นจุดบนส่วนต่อของ $PS$ ที่ทำให้พื้นที่ของ $\Delta P'QR$ เท่ากับ $4$ จะได้ว่า $\Delta P'QR$ เป็นสามเหลี่ยมที่โจทย์ต้องการ 08 ธันวาคม 2016 17:29 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Pitchayut |
#3
|
||||
|
||||
ใช้จากที่ว่า จำนวนนับ $k$ จำนวนเรียงถัดกันจะมี $k!$ เป็นตัวประกอบเสมอและ $2016|8!,2016\nmid 7!$ กระจายๆ จะได้ว่า $$M(n)=\lfloor\frac{3n-1+\sqrt{5n^2-10n+1}}{2}\rfloor$$ ได้คำตอบคือ $\frac{3+\sqrt{5}}{2}$ ได้ไม่ยากว่า $$f(x)=\frac{1}{2}(tan^{-1}x+tan^{-1}(\frac{1}{1-x})-tan^{-1}(\frac{x-1}{x}))$$ ดังนั้น $$\int_{0}^{1}\ f(x)dx =\frac{1}{2}\int_{0}^{1}\left[(tan^{-1}x+tan^{-1}(\frac{1}{1-x})\right] \ dx +\frac{1}{2}\int_{0}^{1}tan^{-1}(\frac{1-x}{x})\ dx$$ ทั้งสองพจน์สามารถจัดการได้โดยการเปลี่ยนตัวแปร $x\rightarrow 1-x$ และใช้เอกลักษณ์ $tan^{-1}x+tan^{-1}(\frac{1}{x})=\frac{\pi}{2}$ พจน์หลังจะได้ค่าเท่ากับ $\frac{\pi}{8}$ พจน์หน้าจัดการได้ค่าเท่ากับ $\frac{\pi}{4}$ สรุปแล้วตอบ $\frac{3\pi}{8}$ แทนแต่ละช่องของตารางด้วยสมาชิกใน matrix ขนาด $(2n-1)\times(2m-1)$ จะระบายสีสี่สี โดยระบายสีที่ 1 ในช่อง $a_{ij}$ ที่ $i$ และ $j$ เป็นจำนวนคี่ โดยระบายสีที่ 2 ในช่อง $a_{ij}$ ที่ $i$ และ $j$ เป็นจำนวนคู่ โดยระบายสีที่ 3 ในช่อง $a_{ij}$ ที่ $i$ เป็นจำนวนคี่ และ $j$ เป็นจำนวนคู่ โดยระบายสีที่ 4 ในช่อง $a_{ij}$ ที่ $i$ เป็นจำนวนคู่ และ $j$ เป็นจำนวนคี่ การปูกระเบื้อจะทับช่องที่มีสีต่างกันเสมอ ดังนั้นจึงต้องใช้สีเท่ากับจำนวนช่องที่มีสีซ้ำกันมากที่สุด (สีที่ 1) ซึ่งมีค่าเท่ากับ $mn$ จาก $e^x\geq x+1$ จะได้ว่า $x_{n+1}=\ell n(e^{x_n}-x_n)\geq\ell n(1)$ หรือก็คือ $x_{n} \geq 0$ สำหรับทุกจำนวนเต็มไม่ติดลบ $n$ (ลำดับมี Lower bound) และจากที่ $x_n\geq 0$ จะได้ว่า $x_{n+1}=\ell n(e^{x_n}-x_n)\leq\ell n(e^{x_n})$ หรือก็คือ $x_{n+1} \leq x_n$ สำหรับทุกจำนวนเต็มไม่ติดลบ $n$ (เป็นลำดับไม่เพิ่ม) ดังนั้นแล้วลำดับนี้ลู่เข้าสู่จำนวนจริง $L$ จำนวนหนึ่ง แสดงต่อได้ไม่ยากว่า $L=0$ และจากที่ $x_{n+1}=\ell n(e^{x_n}-x_n)$ จะได้ว่า $x_n=e^{x_n}-e^{x_{n+1}}$ สำหรับทุกจำนวนนับ $n$ ดังนั้น $$\sum_{n = 0}^{\infty} x_n=\sum_{n = 1}^{\infty}e^{x_n}-e^{x_{n+1}} =e-e^{\lim_{n \to \infty} x_n}=e-1$$ ให้ $O(S(n))=\beta n^{\alpha}$ จะได้ว่า $O(S([n+1]^2))=\beta n^{2\alpha}$ และสังเกตได้ไม่ยากว่า Squarish number จะเขียนอยู่ในรูป $t^2+s^2$ หรือ $(t+1)^2-s^2$ โดยที่ $ 0\leq s^2\leq t$ ดังนั้นแล้วในช่วง $(i^2,(i+1)^2]$ จะมีจำนวน Squarish ทั้งหมด $2\left\lfloor\sqrt{i} \right\rfloor \sim 2\sqrt{i} $ ตัว เมื่อรวมทุกช่วงที่เป็นไปได้ $S((N+1)^2)$ จะมีค่าประมาณ $$2(\sqrt{1}+\sqrt{2}+...+\sqrt{N})\sim 2\int_{0}^{N}\sqrt{x}dx \sim \frac{4}{3}N^{1.5}$$ ดังนั้น $O(S([n+1]^2))=\frac{4}{3} n^{\frac{3}{2}}$ สุดท้ายจะได้ $\alpha = \frac{3}{4},\beta = \frac{4}{3}$ มันคือแบบฝึกหัด Extremal ปกติเลยครับ อันนี้ผมเข้าใจผิดอะไรหรือเปล่า = = พิจารณาสามเหลี่ยมที่มีพื้นที่มากที่สุด แล้ววาดรูปคล้ายกันทั้งสี่ด้าน
__________________
I'm Back 08 ธันวาคม 2016 21:37 : ข้อความนี้ถูกแก้ไขแล้ว 6 ครั้ง, ครั้งล่าสุดโดยคุณ Beatmania |
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
ข้อสอบ EMIC 2016 @ เชียงใหม่ (TIMC2016)(บุคคล+ทีม+คำตอบ) | Ruth Bimbo | ข้อสอบในโรงเรียน ประถมปลาย | 0 | 22 สิงหาคม 2016 22:52 |
ผลการแข่งขัน TIMC 2016 (EMIC2016+IWYMIC2016) | otakung | ข่าวคราวแวดวงประถม ปลาย | 0 | 21 สิงหาคม 2016 19:59 |
ผลสอบ Putnam 2015 -นักศึกษาไทยคนแรกในประวัติศาสตร์ได้รับเลือกเป็น Putnam Fellow | putnam | งานหรือข่าวคราวคณิตศาสตร์ทั่วไป | 1 | 09 เมษายน 2016 09:46 |
สุขสันต์ปีใหม่ 2016 ครับ | จูกัดเหลียง | ฟรีสไตล์ | 5 | 02 มกราคม 2016 16:28 |
ฟุตบอลยูโร 2016 | ฟินิกซ์เหินฟ้า | ฟรีสไตล์ | 5 | 14 กันยายน 2014 19:57 |
|
|