MathDB

4

Part of 2007 QEDMO 5th

Problems(1)

Seven permutations of Z/(nZ) imply that n is coprime to 6

Source: 5th QEDMO problem 4, generalizing a result by Dean Alvis and Michael Kinyon

11/10/2007
Let n n be a positive integer, and let (a1, a2, ..., an) \left( a_{1},\ a_{2} ,\ ...,\ a_{n}\right), (b1, b2, ..., bn) \left( b_{1},\ b_{2},\ ...,\ b_{n}\right) and (c1, c2, ..., cn) \left( c_{1},\ c_{2},\ ...,\ c_{n}\right) be three sequences of integers such that for any two distinct numbers i i and j j from the set {1,2,...,n} \left\{ 1,2,...,n\right\}, none of the seven integers a_{i}\minus{}a_{j}; \left( b_{i}\plus{}c_{i}\right) \minus{}\left( b_{j}\plus{}c_{j}\right); b_{i}\minus{}b_{j}; \left( c_{i}\plus{}a_{i}\right) \minus{}\left( c_{j}\plus{}a_{j}\right); c_{i}\minus{}c_{j}; \left( a_{i}\plus{}b_{i}\right) \minus{}\left( a_{j}\plus{}b_{j}\right); \left( a_{i}\plus{}b_{i}\plus{}c_{i}\right) \minus{}\left( a_{j}\plus{}b_{j}\plus{}c_{j}\right) is divisible by n n. Prove that: a) The number n n is odd. b) The number n n is not divisible by 3 3. [hide="Source of the problem"]Source of the problem: This question is a generalization of one direction of Theorem 2.1 in: Dean Alvis, Michael Kinyon, Birkhoff's Theorem for Panstochastic Matrices, American Mathematical Monthly, 1/2001 (Vol. 108), pp. 28-37. The original Theorem 2.1 is obtained if you require b_{i}\equal{}i and c_{i}\equal{}\minus{}i for all i i, and add in a converse stating that such sequences (a1, a2, ..., an) \left( a_{1},\ a_{2},\ ...,\ a_{n}\right), (b1, b2, ..., bn) \left( b_{1},\ b_{2},\ ...,\ b_{n}\right) and (c1, c2, ..., cn) \left( c_{1} ,\ c_{2},\ ...,\ c_{n}\right) indeed exist if n n is odd and not divisible by 3 3.
modular arithmeticcombinatorics proposedcombinatorics