Tag Archives: competitive Maths exam

Basic enumeration — continued

(a) How many possibilities are there to distribute k forints (Hungarian currency) among n people so that each receive at least one?

(b) Suppose that we do and insist that each person receives something. What will be the number of distributions in this case?

Hint (a)

Imagine k 1-forint coins in a row and suppose that the people come one by one and pick up forints as long as you allow them.

Hint (b)

Reduce to the previous case by borrowing 1 forint from each person.

Solution (a):

If we distribute the forints by the procedure described in the hint, we have to say “Next please” n-1 times. If we determine at which points (after which coins) we say this we uniquely determine the distribution. There are

k-1 possible points to switch and we have to choose n-1 out of these. Hence, the result is

{{k-1} \choose {n-1}}.

Solution (b):

Borrow one forint from each person. If we distribute the n+k forints, we then have in such a way that each person gets at least one, we should then have done the same as if we had distributed the k forints without this requirement. More precisely, distributions of n+k forints among persons so that each one gets at least one are in one to one correspondence with all distributions of n forints among k persons. Hence, the answer is

{{n+k-1} \choose {n-1}}.

More later,

Nalin Pithwa

References for RMO, INMO and IMO

Below is a list of basic references for RMO, INMO and IMO:

  • Problem Primer for the Olympiad by C R Pranesachar, B J Venkatachala et al.
  • Higher Algebra by Hall and Knight
  • Higher Algebra by Bernard and Child
  • Plane Trigonometry Part I by S L Loney
  • A School Geometry by Hall and Stevens
  • An Introduction to Number Theory by Niven and Zuckermann
  • Elementary Number Theory by David M Burton
  • Problem Solving Strategies by Arthur Engel
  • Problems in Plane Geometry by Sharygin, MIR Publishers.
  • Combinatorics — Schaum Series
  • Mathematical Circles by Fomin et al.
  • An Excursion in Mathematics by M R Modak
  • Selected Problems and Theorems in Elementary Mathematics by Shklyarsky et al.
  • International Mathematical Olympiads, 1959-77, S. L. Greitzer.
  • International Mathematical Olympiads, 1978-85, M. S. Klamkin
  • USA Mathematical Olympiads, 1972-85, M. S. Klamkin
  • Mathematical Challenges for Olympiads, 2nd edition, C R Pranesachar et al.
  • An Excursion in Mathematics — M. R. Modak,
  • College Geometry — Howard Eve.
  • 1000 Mathematical Challenges — J N Kapur

Start cracking …

Nalin Pithwa