There are $100$ dwarfes with weight $1,2,...,100$. They sit on the left riverside. They can not swim, but they have one boat with capacity 100. River has strong river flow, so every dwarf has power only for one passage from right side to left as oarsman. On every passage can be only one oarsman. Can all dwarfes get to right riverside?
Problem
Source: All Russian Olympiad 2017,Day1,grade 9,P3
Tags: number theory, combinatorics
PROF65
03.05.2017 18:28
if it means ''one passage from right side to left or the other direction as oarsman'' then: we have a total weight of $50 \times 101$ so we need at least $ 51$ voyages from left to right but we need also $50$ voyages from right to left to get back the boat hence there must be $101$ oarsman which is impossible . RH HAS
RagvaloD
03.05.2017 18:39
PROF65 wrote: if it means ''one passage from right side to left or the other direction as oarsman'' No, it means, that for other direction dwarf have always enough power. But from right to left only for one passage.
MellowMelon
03.05.2017 18:47
Generalize 100 to $n$. If there are $k$ voyages to the left, then there are $k-1$ voyages to the right that must each use a different oarsman. There's no point in the weight $n$ dwarf crossing right to left, so we assume $k \leq n$. The total weight that goes from right to left is at least
\[1+2+\cdots+(k-1) = \frac{k(k-1)}{2}. \]This means for all the dwarves to cross, the total weight that goes from left to right must be at least
\[ 1+2+\cdots+n+\frac{k(k-1)}{2} = \frac{n(n+1)}{2} + \frac{k(k-1)}{2}. \]This quantity must also be at most $nk$, since there are $k$ left-to-right voyages each with total weight at most $n$. Setting up that inequality and simplifying gives
\[ (k-n-1)(k-n) \leq 0. \]Since $k \leq n$, we have $k = n$ and equality holds in all of our bounds.
The interesting part of this problem is that if $n$ is odd, there actually is a way for the dwarves to cross. For $1 \leq i \leq (n-1)/2$, the $i$th trip sends dwarves $i,n-i$ to the right and dwarf $i$ rows back. Next, dwarf $n$ goes to the right, and the boat is on the right side now. For $1 \leq i \leq (n-1)/2$, the next $i$ trips are dwarf $n-i$ rowing back and dwarves $i,n-i$ returning.
If $n$ is even, things break down due to the existence of dwarf $n/2$. First, since there is equality in the above bounds, every trip from left to right has total weight $n$, and all dwarves of weight less than $n$ cross left to right twice. This means the weight $n-1$ dwarf must cross left to right with the weight 1 dwarf twice. Since the weight 1 dwarf can't cross with anyone else, the weight $n-2$ dwarf must cross with the weight 2 dwarf twice. By induction on this pattern, we find that the weight $n-k$ dwarf crosses with the weight $k$ dwarf twice for $1 \leq k \leq n/2 - 1$. That leaves no one for the weight $n/2$ dwarf to cross with, so $n$ even is impossible.
roughlife
11.06.2017 15:36
i. They need left-way trip 100 times pf) assume that they did left-way trip only k-times(0<k<100), a_{1},...,a_{k} who are oarsman. So right-way trips occur (k+1) times. Let's s_{k} be total capacity of every right-way trip. s_{k}=2(a_{1}+...+a_{k})+(5050-(a_{1}+...+a_{k})=5050+(a_{1}+...+a_{k}). Therefore there must be a right-way trip above s_{k}/(k+1) capacity. But (a_{1}+...a_{k})>=k(k+1)/2, so s_{k}/(k+1)>100. contradiction. ii. now that left-way trip occurs 100 times, right-way trip occurs 101 times and total capacity of right-way trip is 5050*2=10100. so, one right-way trip must carry full-capacity it could afford. however, dwarf with weight 50 is impossible. because 99 should be with 1, 98 should be with 2 .... done.
TheImaginaryOne
14.12.2018 08:14
Claim: Firstly a process where not all dwarves ever become oarsmen can be converted into a process where all dwarves are oarsmen. Then if a process where not all dwarves are oarsmen exist, then a process where all dwarves are oarsmen exist too. After the original process, let the dwarves that have not become oarsmen be $D_1,D_2\dots D_n$ After the original process, do as follows: For each $D_i$, $D_i$ does a backwards journey (becoming oarsmen) and then does a forwards journey by itself, going back to the other side. Repeat for all $D_i$, this gives our new process. This means it suffices to prove that processes where all dwarves are oarsmen doesn't exist. Assume it does exist. Then there are 100 backwards journeys, so 101 forwards journeys. The total mass of all forward journeys is at most 10100. But as each dwarf $m$ travels one forward journey, goes back and does one more, it contributes $2m$ to the total, so the total is $2(1+\dots+100)=10100$ exactly. Equality holds so all forward journeys is exactly a mass of 100. Induction: all dwarves of mass $51\le x \le 99$ must go on a forward journey with dwarf $100-x$ We strongly induct: for all $x \ge k$ the proposition is true. For some dwarf $y \le 100-k$ and the dwarf $100-y$, both have two forward journeys, and both times the $100-y$ dwarf pairs with $y$ (inductive hypothesis, note $100-y \ge k$), so the dwarf $y$ can't go on any other journeys, so it can't pair with $k-1$. Thus the dwarf $k-1$ can only pair with the dwarf $101-x$. For the base case, the dwarf 99 can only pair with the dwarf 1. Induction done But as all dwarves $1,\dots 49$ pair to $51, \dots 99$, then dwarf $50$ can only be paired with another dwarf $50$, but there is only one of them! Contradiction.
Gomes17
11.08.2020 04:36
Call all dwarfs weighting at least $50$ heavy, otherwise call them light. Finally, say that a Right-Left trip is unreasonable if the oarsman is heavy, otherwise it is reasonable. Notice that in each trip, at most one heavy dwarf gets transported. If the number of unreasonable trips is $x$, we see that there are $51+x$ times in which a heavy dwarf goes from left to right. This means that there are at least $50+x$ times the boat returns, therefore at least $50$ of these trips are reasonable. But there are $49$ light dwarfs only, contradiction.
mathaddiction
23.08.2020 16:19
The answer is no. Suppose that the dwarfes are $A_1,A_2,...,A_{100}$ and suppose dwarf $A_i$ has weight $i$. The crucial observation is to consider the set $S=\{A_{50},A_{51},...,A_{100}\}$. Notice that two dwarfes from $S$ can not travel together. Now suppose $k$ dwarfes in $S$ has travel from right riverside to left riverside. Then the boat has travelled at least $|S|+k=51+k$ times from left to right. Meanwhile, from the condition, each of $A_1,...,A_{49}$ only travel from right riverside to left riverside at most once. Therefore the boat has travelled at most $49+k$ times from right to left, contradiction.