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

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$ نمی پوشاند.پس برای پوشاندن $2n+1$ نقطه از $A(n)-A(n-1)$ دایره لازم است.اما در هر مرحله این نقاط ممکن است قبلن به کمک دایره های دیگر پوشانده شده باشند مثلن نقطه $(8,1))$ و $(1,8)$ که در مرحله $8$ قرار دارد قبلن در مرحله $7$ توسط دایرۀ $x^2+y^2=7^2+4^2 $ پوشانده شده است.با این توضیحات اگر در مرحلۀ $n+1$ نقطه‌ای مانند $(n+1,k)$ قبلن به کمک دایره گذرنده از مثلن $(m,s)$ پوشانده شده باشد باید از مجموع ما حذف شود.پس اگر قرار دهیم:

$X(n+1)=[k|0 \leq k \leq n+1 \wedge \exists m,s|1 \leq m \leq \leq n,0 \leq s \leq m,(n+1)^2=m^2+s^2-k^2]$

$S(n+1)=S(n)+n+2-S(X(n+1))$

$ \Box $

Comments

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