پوشاندن نقاط صفحه

Question

فرض کنید : $$A= \lbrace (x,y)\in R^2- \lbrace(0,0)\rbrace \ | \ x,y\in \lbrace 0,1,...,n\rbrace \rbrace $$ نشان دهید حداقل تعداد دایره های لازم به مرکز مبدا مختصات برای پوشاندن تمام نقاط مجموعه $A$ , $n$ است .

Comments

احتمالا دایره های مورد نظر شما شرط دیگری هم داشته اند که از قلم افتاده است چرا که دایره ای به شعاع به اندازه کافی بزرگ می تواند تمام نقاط را مجموعه مفروض را بپوشاند.

---

![enter image description here][1]


  [1]: http://math.irancircle.com/?qa=blob&qa_blobid=4924268313009648947

---

@N منظور از پوشاندن، پوشاندن با سطح داخلی دایره نبوده‌است بلکه با مرز دایره (محیطش) بوده‌است. @farhad پرسش را درست متوجه شده‌اند و کاملا درست می‌گویند که حداقل تعداد دایره‌های لازم بیشتر از $n$ است. و خواستهٔ پرسش تنها با در نظر گرفتن $n$ نقطهٔ روی یک سمت یکی از محورها به صورت بدیهی ثابت می‌شود.

Answer 1

مجموعه $A$ تعریف شده در صورت مسأله را مربع مطلوب $n \times n$ مینامیم و تعداد دایره های لازم برای پوشاندن این مربع را $S(n)$ تعریف می کنیم.

در مربع مطلوب $n \times n$ هر نقطه دلخواه $(k,n-k)$ که $0 \leq k \leq n$ به کمک دایره $x^2+y^2=k^2+(n-k)^2$ پوشانده می شود و این دایره نقطه $(n-k,k)$ را نیز می پوشاند و چون در ربع اول هر دایره به مرکز مبدأ یک بیک است نقاط به صورت $(s,t)$ را که $0 \leq s,t \leq n$ و $k \neq s$ و $t \neq n-k$ نمی پوشاند.

از طرفی دیگر دایره $x^2+y^2=k^2+(n-k)^2$ که $0 \leq k \leq n$ از هیچ کدام از نقاط $(n+1-m,m)$ یا $(m,n+1-m)$ که $0 \leq m \leq n+1$ نمیگذرد زیرا در غیر اینصورت یک $m$ که $0 \leq m \leq n+1$ وجود دارد:

$m^2+(n+1-m)^2=k^2+(n-k)^2 \Rightarrow 2m^2+(n+1)^2-2m(n+1)=2k^2+n^2-2nk$

$ \Rightarrow 2m^2-2k^2-2m(n+1)+2nk=n^2-(n+1)^2=-2n-1 \bot $

زیرا یک طرف زوج و یک طرف فرد است.بنابر این:

$S(n+1)=S(n)+n+2 \Rightarrow S(n)=\frac{1}{2} (n+1)(n+2)-1$

$ \Box $

Comments

با عرض معذرت اثبات من در مرحله آخر ایراد دارد.باید به جای n+1 قرار داد n+m .
امیدوارم بتوانم ایراد را رفع و کامل کنم.