Minimum markers in a coverage model
Minimum markers in a coverage model
The video could not load. Check your connection and try again, or download it directly.
Download video
Open Chinese transcript
- 这是抽象覆盖模型,不代表真实摄像头视野。1到5号门排成一列,一个标记只覆盖自己和紧邻门。
- 一个标记最多覆盖连续3个门,所以单个标记不可能覆盖5个门,至少需要2个。
- 把一个标记放2号,它覆盖1、2、3号。
- 另一个放4号,它覆盖3、4、5号。两个范围合起来覆盖全部五门。
- 下界说至少2个,构造又用2个做到,所以最少正好是2个。
- 现在改成1到4号门,规则不变。请圈出最少标记及各自覆盖范围,小宝贝到你了。
Sources for this explanation
Logical thinking
Prove a lower bound from maximum coverage, then give a placement meeting that bound.
Worked example
In this abstract model, doors 1–5 are in a line; a marker covers its door and immediate neighbors. Minimum markers to cover all doors?
One marker covers at most three consecutive doors, so one is insufficient; markers at 2 and 4 cover all five.
Try one question
One covers at most 3 doors; two can cover all 4.