One wants to distribute $n$ same sized cakes between $k$ people equally by cutting every cake at most once. If the number of positive divisors of $n$ is denoted as $d(n)$, show that the number of different values of $k$ which makes such distribution possible is $n+d(n)$
Problem
Source: Turkey NMO 2001 Problem 3
Tags: combinatorics proposed, combinatorics
SCP
01.10.2011 21:30
For $n=30$ we have $n+d(n)=72>2n$, so how can it be possible when we have each cake in at most $2$ parts?
mavropnevma
02.10.2011 00:07
Well, for $n=30$ we have $n+d(n)=38$, since $30=2^1\cdot 3^1\cdot 5^1$, so $d(30) = (1+1)(1+1)(1+1) = 8$.
mahanmath
02.10.2011 01:18
Not hard to see if $k\leq n$ then it`s possible to do such distribution , so it leaves us with case $k>n$ and we hope that all the ''good'' $k$ are equal to $n+t$ where $t$ is a divisor of $n$ .
Construct a graph with $k$ vertex (it represents people) and connect two people iff they share a cake , note that $k>n$ implies that all cakes should be cut , so this graph has $n$ edge .
A more important observation is that, this graph has no cycle .
If it has a cycle of length $p$ then we have $p$ person who divide (at least) $p$ cakes between themselves , but it contradicts the assumption that each person has less than one cake (remember that $k>n$) .
So our graph consist of some trees (connectivity components).
Next note that $\frac{number\:of\:people\:in\:tree}{number \: of\: edges\: of\: tree}$ should be same for all trees in our graph . So to finish our proof we just need to konw in every trees we have exactly one more vertex than edges .
(There are some details which I prefer to left to the reader )