Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the following question, one has to find the most convenient x-y-z co-ordinates in a building for a group of employees to sit together. I have tried finding individual average values for x, y & z but that didn't work. Moreover, a time-efficient approach is what I'm looking for.

Problem Statement -

Each floor in an IT office is arranged in a rectangular array of M×N cubicles. Cubicles on floor F are identified by coordinates (1, 1, F) to (M,N, F). There are connections between a cubicle and its neighbors on the floor. Each cubicle is also connected vertically to the corresponding cubicle one floor above and one floor below. Thus, from a given cubicle (i, j, k) on floor k, an employee can go across to one of its four neighbors (i+1, j, k), (i−1, j, k), (i, j+1, k), (i, j−1, k) on the same floor. He can also go up one floor to reach the cubicle (i, j, k+1) or down one floor to reach the cubicle (i, j, k−1).

It takes 2 units of effort for an employee to cross to a neighboring cubicle on the same floor. It takes 1 unit of effort to go to the corresponding cubicle one floor below. It costs 3 units of effort for an employee to go to the corresponding cubicle one floor up.

A group of employees want to meet to discuss something. They would like to meet in a cubicle located so that their overall effort to reach the meeting place is minimized. The cubicle where they meet can be anywhere in the building —it need not be one in which one of them sits. For instance, suppose that there are 5 employees who sit in cubicles with coordinates (28,3,17), (8,36,48), (6,36,31), (50,24,15) and (12,28,32). Then, the best cubicle for them to meet is the one at (12,28,17).

In the three problems below, you are given the list of cubicles where a group of employees sit. Your task is to identify the coordinates of the optimum cubicle for them to meet.

(a) 13 people seated in cubicles (36,90,7), (77,69,7), (75,22,7), (43,30,7), (75,62,7), (70,23,7), (76,30,7), (25,28,7), (95,56,7), (3,25,7), (51,98,7), (2,11,7), (46,46,7).

(b) 25 people seated in cubicles (51,1,73), (61,1,33), (1,1,34), (46,1,38), (23,1,94), (91,1,89), (11,1,89), (10,1,70), (37,1,73), (96,1,93), (44,1,50), (16,1,81), (50,1,28), (50,1,84), (55,1,60), (48,1,97), (3,1,62), (92,1,84), (27,1,22), (100,1,51), (59,1,31), (8,1,39), (55,1,47), (50,1,1), (33,1,45).

(c) 21 people seated in cubicles (18,72,69), (12,81,43), (40,19,33), (40,60,48), (2,78,66), (14,78,84), (70,25,3), (48,59,43), (29,4,10), (12,96,1), (89,13,74), (57,26,54), (100,32,39), (99,38,65), (13,40,43), (79,20,20), (28,91,12), (98,38,37), (40,34,41), (16,46,36), (18,1,16).

Source - Zonal Informatics Olympiad 2007 Question Paper

Thanks!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

A hint:

(a) Begin by considering the analogous one-dimensional problem: You are given $n$ integers $x_k$ between $0$ and $M$. How should you choose $\xi\in{\mathbb Z}$ such that $s:=\sum_{k=1}^n |x_k-\xi|$ is minimal? Draw a figure, choose a trial $\xi$ and check how $s$ changes when $\xi$ is moved right or left.

(b) Note that savings by going diagonally are excluded. It follows that you can solve the problem for the three directions separately.

(c) The experiment made in (a) also helps when investigating the cost of the vertical movement. Note that the employees will have to go back to their own offices after the meeting; so maybe the vertical movement is symmetric after all, either.

share|improve this answer
    
Can you please elaborate on that? By the way, this isn't a homework problem. –  7Aces Oct 30 '12 at 10:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.