Maths Olympiad Prep

Library / /2 of 10

Combinatorics Difficulty 6.1 National olympiad Find the answer

Let nn be a positive integer and pp a fixed prime. We have a deck of nn cards, numbered 1, 2,, n1,\ 2,\ldots,\ n and pp boxes for put the cards on them. Determine all posible integers nn for which is possible to distribute the cards in the boxes in such a way the sum of the numbers of the cards in each box is the same.

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

Solution

Given:

- n n is a positive integer,
- p p is a fixed prime number,
- We have a deck of n n cards, numbered 1,2,,n 1, 2, \ldots, n ,
- We have p p boxes to put the cards into,
- We need to distribute the cards into these boxes such that the sum of the numbers on the cards in each box is the same.

We want to determine all possible integers n n for which it is possible to distribute the cards in this manner.

### Analysis:

Each card has a number from 1 to n n . The total sum of all card numbers is:

S=n(n+1)2 S = \frac{n(n+1)}{2}

To divide S S equally among p p boxes, S S must be divisible by p p . Therefore, we have the condition:

n(n+1)20(modp) \frac{n(n+1)}{2} \equiv 0 \pmod{p}

### Consideration of Congruences:

1. For n(n+1)20(modp) \frac{n(n+1)}{2} \equiv 0 \pmod{p} , either n0(modp) n \equiv 0 \pmod{p} or n+10(modp) n+1 \equiv 0 \pmod{p} must be true because exactly one of n n or n+1 n+1 is divisible by any prime p p .

2. Also, n(n+1)2 \frac{n(n+1)}{2} must be divisible by p p in its entirety. For this to be true, if one term contributes a factor of p p , the other term should must satisfy the divisibility of 2 to make the entire expression divisible by p p .

This condition implies both need further analysis on how multiples of p p can adjust in sequences of consecutive numbers.

### Main Derivation:

To fulfill n(n+1)20(modp) \frac{n(n+1)}{2} \equiv 0 \pmod{p} , we reduce:

- If n0(modp2) n \equiv 0 \pmod{p^2} , then n=kp2 n = kp^2 satisfies the equal distribution because n(n+1)/2 n(n+1)/2 would then include the factor p2 p^2 , making the distribution divisible and feasible:

Given n=kp2 n = kp^2 :

S=(kp2)((kp2)+1)2=k2p4+k2p22 S = \frac{(kp^2)((kp^2)+1)}{2} = \frac{k^2p^4+k^2p^2}{2}

Here, p4 p^4 ensures divisibility by p p (and p2 p^2 ) from the construction.

Thus for even distribution among p p boxes \Rightarrow n=kp2 n = kp^2 .

Thus, the possible integers n n satisfying the condition is of the form:
n=kp2 \boxed{n = kp^2}

This satisfies all conditions required by the problem statement for distributing the card sums evenly across p p boxes.

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.