Dwarves at the river

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Dwarves at the river

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Stage PreIMO 2018 - Italy

The post below has been deleted. Click to close.

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

37 posts

#1 h Apr 23, 2022, 12:27 PM

Y by

There are $100$ dwarves, whose weigths are $1,\,2,\dots,\,100\,\text{kg}$ , who want to cross a river. They have a small boat which can lift at most $100\,\text{kg}$ each time without sinking. For each journey of the boat a non-empty subset of the dwarves to be taken to the other side is chosen and one of these dwarves is chosen as the $\emph{rower}$ for that journey. Since return journeys are counter-current, no dwarf is able to do the rower for more than one return journey. Is it possible for all the dwarves to reach the other side of the river?

Z K Y

The post below has been deleted. Click to close.

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

4 posts

Radin_

#2 h Apr 5, 2025, 5:59 AM

Y by

we claim that the answer is no
assume the contrary, all the dwarves have crossed the river with $n$ trips in the direction of the destination this means that $n-1$ rowers have been on the return journey. the weight moved in each of the n trips to the other side of the river have moved at most $100 kgs$ of weight each and the $n-1$ rowers have moved at least $1+2+\cdots+(n-1)$ back so as all of the dwarves have crossed the river we see that:
$100n-\frac{n(n-1)}{2} \geq 1+2+\cdots +100=\frac{100\cdot101}{2}$
by some simple manipulation this is equivalent to:
$(n-100)(n-101)\leq 0$
so as $n$ is an integer $n=100$ or $n=101$ but most important is that equality must hold meaning dwarves weighing $1$ to $99kgs$ must all cross the river twice and each crossing must be on a boat with passengers weighing $100kgs$ exactly so both of the crossings of 99 must have weight 100 we see that both the crossing must be with 1 so dwarves 99 and 1 only cross the river together the same applies to dwarves 98 and 2 and dwarves 97 and 3 and $\cdots$ and dwarves 49 and 51 but this means that 50 must cross the river alone(as all the other dwarves have travelled in pairs)but dwarf 50 also must do each crossing on a boat with total weight of 100 which is a contradiction.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a