Putnam 1950 B1

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Putnam 1950 B1

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4736 posts

#1 h May 25, 2022, 1:58 AM • 2 Y

Y by Mogmog8, the_mathmagician

In each of $n$ houses on a straight street are one or more boys. At what point should all the boys meet so that the sum of the distances that they walk is as small as possible?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7322 posts

DottedCaculator

#2 h May 29, 2022, 8:06 PM • 1 Y

Y by centslordm

the median

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

123 posts

KAME06

#3 h Mar 25, 2025, 6:19 PM • 1 Y

Y by centslordm

Consider the street as a line and the houses as ordered points $H_1, H_2, ..., H_n$ . Let $M$ the meeting point.
If $n=2k$ , notice that if $M$ is not on $H_iH_{2k+1-i}$ , we can say $|H_i-M|>|H_i-H_{2k+1-i}|$ or $|H_{2k+1-i}-M|>|H_i-H_{2k+1-i}|$ . If $M$ is on $H_iH_{2k+1-i}$ , $|H_i-M|+|H_{2k+1-i}-M| = |H_i-H_{2k+1-i}|$ . We conclude that $|H_i-M|+|H_{2k+1-i}-M| \ge |H_i-H_{2k+1-i}|$ , for all $i=1, 2, ..., k$ .
Adding: $\sum_{i=1}^{2k} |H_i-M| \ge \sum_{i=1}^k |H_i-H_{2k+1-i}|$ . To achieve the equality note that, by definition, $H_{i+1}H_{2k+1-(i+1)} \in H_iH_{2k+1-i}$ for $i=1, 2, ..., k-1$ . $M$ must be on $H_kH_{k+1}$ .
If $n=2k+1$ , notice that if $M$ is not on $H_iH_{2k+2-i}$ , we can say $|H_i-M|>|H_i-H_{2k+2-i}|$ or $|H_{2k+2-i}-M|>|H_i-H_{2k+2-i}|$ . If $M$ is on $H_iH_{2k+2-i}$ , $|H_i-M|+|H_{2k+2-i}-M| = |H_i-H_{2k+2-i}|$ . We conclude that $|H_i-M|+|H_{2k+2-i}-M| \ge |H_i-H_{2k+2-i}|$ , for all $i=1, 2, ..., k$ . Moreover, $|H_{k+1}-M| \ge 0$ .
Adding: $\sum_{i=1}^{2k} |H_i-M| \ge \sum_{i=1}^k |H_i-H_{2k+2-i}| + 0$ . To achieve the equality note that, by definition, $H_{i+1}H_{2k+2-(i+1)} \in H_iH_{2k+2-i}$ for $i=1, 2, ..., k-1$ and $|H_{k+1}-M| = 0$ if and only if $M=H_{k+1}$ .
$H_{k+1}$ is on $H_kH_{k+2}$ , so $M$ must be on $H_{k+1}$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a