A teacher at a school with grades 1 through k wants a schedule, repeated every k years, in which she...

combinatorics/teaching.schedule New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

A teacher at a school with grades 1 through k wants a schedule, repeated
every k years, in which she teaches each grade exactly once and never
teaches a class she has taught before.  For which k is this possible?

You may recall the story of the unfortunate teacher who transferred to
a school with grades 1 through 6, only to find that there was no
repeatable schedule for teaching each of those six grades every six
years without ever teaching the grade that some of her former students
are in.

Now our teacher has a chance to transfer to a school in a new country.
This country has an unusual system: every school teaches grades
numbered 1 consecutively up to some number, which can be very high.
For example, there is a school teaching grades 1 through 5, another
teaching grades 1 through 10, and another teaching grades 1 through 17.
Also, at all these schools, new teachers are allowed to design their
own schedule saying which grade they will teach each year.

-- David Karr <karr@cs.cornell.edu> (August 1994)

[ Editor: the opening sentence is the editor's summary; the original
posting's question is not quoted in full in the collected material. ]

Show solution

No, I'm not on drugs - there really is a connection between this
puzzle and juggling.

[i.e. if she teaches grade 3 then grade 4 it is possible she will meet
some of her previous students the second year]

As a rec.juggling supergenius (tm) I can tell you that 1-5 works, 1-10
does not and 1-17 does.  In fact 1-2n never works and 1-2n+1 always
has at least one working schedule.

Now, would some other rec.juggler like to explain how I know this?

-- Alan Morgan <alanm@gateway.efi.com>

Surely.  Imagine that every class that starts school receives a ball
from the class that's been taught by the teacher the year before.  As
the teacher never teaches her old students again, the same set of
balls will be "juggled" all the time.  If we assign to each starting
class the number of years it will hold its ball, we get a sequence of
numbers that's known as a siteswap in jugglespeak.  The problem of
finding a teaching schedule such that the teacher can teach each of k
grades exactly once and repeat the schedule every k years corresponds
to finding a siteswap with period k where each of the numbers 1..k
occurs exactly once.  Every siteswapper knows that the mean of the
numbers in a siteswap is an integer (in fact, it's the number of
objects juggled); however, the mean of 1,2,...,2n is n + 1/2, so there
can be no such siteswap with period 2n.  OTOH, it's well known that
1 2 3 ... 2k+1 is a siteswap for any k.  Hence your conclusion.  I was
a bit hazy about some details, but that's the general idea.

Nice problem!  Thanks.

-- Taneli Huuskonen <huuskone@cc.Helsinki.FI> (rec.puzzles and
   rec.juggling, August 1994)