There are n stationary cell-phones c1, ..., cn and n stationary cell-phone tower

Question

There are n stationary cell-phones c1, ..., cn and n stationary cell-phone towers t1, ..., tn. The distances between cell-phones and towers are given to you in an n × n matrix d, where d[i, j] denotes the distance between phone ci and tower tj . It is possible for a cell-phone ci to connect to a tower tj if and only if the distance between ci and tj is at most D, where D is the connecting radius. Furthermore, at one time, a cell-phone can connect to at most one tower and a tower can allow at most one connection. Your job is to figure out whether all cell-phones are usable simultaneously. That is, whether it is possible for all cell-phones to connect simultaneously to distinct towers

Consider a simple example with 5 cell-phones and 5 towers. Let the connecting radius be D = 2 miles. The distance matrix for this example is given above.

State true or false: It is possible for all 5 cell-phones to simultaneously connect to distinct towers for this example and give your reasoning.

Explanation / Answer

according to given function:

d[i][j] <=2

then connect cell phone i to tower j

now for i=1:

d[i][1]=1 d[i][2]= 2 <=2 so we can connect the cell phone 1 to either tower 1 or 2

now for i=2:

d[i][2]= d[i][3]=1 <=2 so we can connect the cellphone 2 to either tower2 or 3

now for i=3:

d[i][3]= 2 d[i][4]=1 <=2 so we can connect the cellphone 3 to either tower 3 or 4

now for i=4:

d[i][4]= 1 d[i][5]=1 <=2 so we can connect the cellphone 4 to either tower 4 or 5

So, lets consider we have connected the phone 4 to tower 5:

so, now the phone 3 can be connected to tower4

and phone 2 can be connected to tower 3

now the phone 1 can be connected to either tower 1 or 2

But when i=5, we can see that phone 5 can only be connected to tower1.

So we have to connect the phone 1 to tower2.

Hence the given statement is True.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.