早教吧 育儿知识 作业答案 考试题库 百科 知识分享

平面上有n个点,任意两点间的距离是不小于1的,求证:两点间距离等于1的点对数不超过3n.

题目详情
平面上有n个点,任意两点间的距离是不小于1的,求证:两点间距离等于1的点对数不超过3n.
▼优质解答
答案和解析
以0.5为半径对每个点画圆发现每个圆最多有六个圆与其相切
也就是每点最多有6个点与其距离等于1
n个点就有6n个 每两点算一对
每对重复一次(就是假设x0周围有六个点x1,x2,x3,x4,x5,x6与其距离等于1,而算x1周围点的时候又把x0算一次)也就是最多有6n/2=3n个