Tagged: numbers

Coursera FB problem

 Find 11 positive integers such that none of them add up to a multiple of 11, or prove that this cannot be done.

The above problem was posted on the FB page of the Coursera Introduction to mathematical thinking mooc.

To begin with I misunderstood the problem,  however reading posts by other members of the group  it became clear what the problem was and of how to proceed. This provided a very interesting experience of being in a virtual classroom.

I began the problem after my Japanese class on Tuesday night reading it on my iPhone in my car  — please note that the car was stationary:) The final insight was provided by a fellow classmates posting several hours later as I got out of bed.

I am adding my attempt at understanding this problem below for the sake of interest. As discussed on the group I am looking at a smaller number to begin with ie showing the case for 3 positive integers:

  • a, b, and c are +ve ints
  • none of a, b, or c are divisible by 3
  • hence a, b, and c leave remainder 1 or 2 when divided by 3
  • we want to form the sums a+b, a+c, b+c, and a+b+c and to see what the remainder is when divided by 3
  • it suffices to add the remainders of a, b, and c
    • eg consider 4 and 8
    • 4 leaves remainder 1 when divided by 3
    • 8 leaves remainder 2 when divided by 3
    • 4 + 8 = 12 leaves remainder 0 when divided by 12
    • however the remainders of 4 and 8 when we add them gives 1 + 2 = 3 but note that in terms of dividing by 3 a remainder of 3 is the same as a remainder of 0
    • in mathematical notation we say 1+ 2 = 3 ≡ 0 (mod3)
    • similarly consider 4 and 7, both leave remainder 1 when divided by 3
    • 4 + 7 = 11 which leaves a remainder of 2 when divided by 3
    • note that the remainders of 4 and 7 are both 1 and that when we add these we get 2

a

b

c

a+b

a+c

b+c

a+b+c

Remainder

1

1

1

2

2

2

3 ≡ 0 (mod3)

Remainder

1

1

2

2

2

3

4 ≡ 1 (mod3)

Remainder

1

2

2

3

3

4

5 ≡ 2 (mod3)

Remainder

1

2

1

3

2

3

4

Remainder

2

2

2

4

4

4

6 ≡ 0 (mod3)

Remainder

2

2

1

4

3

3

5

Remainder

2

1

1

3

3

2

4

Remainder

2

1

2

3

4

3

5
  • notice that in each row there always occurs at least one cell in which there is a 3 or a 6 (≡ 0 (mod3) ie divisible by 3).
  • with the necessary changes being made it would be possible to show that for any set containing n positive integers there must be at least one way of combining the numbers in the set to form a sum which is divisible by n.