Lucky Seven

Probability Level pending

Let X = { 1 , 2 , 3 , . . . 100 } \mathbb{X}=\{1,2,3,...100\} and Y \mathbb{Y} be a non empty subset of X \mathbb{X} such that the sum of no two elements in Y \mathbb{Y} is divisible by 7 7 . Find the maximum possible number of elements in Y \mathbb{Y} .


The answer is 45.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Neha Kannan
Jun 3, 2015

Let A i A_{i} be a subset of X such that A i A_{i} = 7 n + i 7n+i n I n \in \mathbb{I}

A 0 = { 7 , 14 , 21 , . . . . 98 } A_{0}=\{7,14,21,....98\}

A 1 = { 1 , 8 , 15 , . . . . . 99 } A_{1}=\{1,8,15,.....99\}

A 2 = { 2 , 9 , 16 , . . . . 100 } A_{2}=\{2,9,16,....100\}

A 3 = { 3 , 10 , 17 , . . . . 94 } A_{3}=\{3,10,17,....94\}

A 4 = { 4 , 11 , 18 , . . . . 95 } A_{4}=\{4,11,18,....95\}

A 5 = { 5 , 12 , 19 , . . . . 96 } A_{5}=\{5,12,19,....96\}

A 6 = { 6 , 13 , 20 , . . . . 97 } A_{6}=\{6,13,20,....97\}

Number of elements in A 0 = 14 A_{0}=14

A 1 = 15 A_{1}=15

A 2 = 15 A_{2}=15

A 3 = 14 A_{3}=14

A 4 = 14 A_{4}=14

A 5 = 14 A_{5}=14

A 6 = 14 A_{6}=14

If we select an element from A 1 A_{1} , no element from A 6 A_{6} can be selected as the sum of the two elements would be divisible by 7.

So for maximum possible elements Y should have : 1 element from A 0 A_{0} ,15 elements from A 1 A_{1} , 15 elements from A 2 A_{2} and 14 elements from either A 3 A_{3} or A 4 A_{4} .

So the maximum possible number of elements = 1 + 15 + 15 + 14 = 45 =1+15+15+14 =\boxed{45}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...