Maths Olympiad Prep

Library / /30 of 97

Combinatorics Difficulty 7.7 National olympiad, round 2 Find the answer

101101 people, sitting at a round table in any order, had 1,2,...,1011,2,... , 101 cards, respectively.
A transfer is someone give one card to one of the two people adjacent to him.
Find the smallest positive integer kk such that there always can through no more than k k times transfer, each person hold cards of the same number, regardless of the sitting order.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given 101 people sitting at a round table, each holding a unique card numbered from 1 to 101, we need to determine the smallest positive integer k k such that through no more than k k transfers, each person can hold the same number of cards, regardless of the initial sitting order.

To find the smallest k k , we consider the value S S defined as:
S=i=151iai+i=150ibi, S = \sum_{i=1}^{51} i a_i + \sum_{i=1}^{50} i b_i,
where ai a_i represents the number of cards held by people in odd positions (1, 3, 5, ..., 101) and bi b_i represents the number of cards held by people in even positions (2, 4, 6, ..., 100).

Initially, the value of S S at the internal position is:
S=i=151i(2i1)+i=1502i2. S = \sum_{i=1}^{51} i (2i-1) + \sum_{i=1}^{50} 2i^2.

At the terminal position, where each person has the same number of cards, the value of S S is:
S=i=15151i+i=15051i. S = \sum_{i=1}^{51} 51i + \sum_{i=1}^{50} 51i.

The change in S S , denoted as ΔS \Delta S , is:
ΔS=42925. \Delta S = 42925.

Since each transfer changes the value of S S by at most 1 (either increasing or decreasing it by 1), it follows that at least 42925 steps are required to equalize the number of cards held by each person.

Therefore, the smallest positive integer k k such that each person can hold the same number of cards through no more than k k transfers is:
\[
\boxed{42925}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.