Given-a-set-H-1-2-3-300-We-will-a-create-a-subset-of-H-consisting-of-three-elements-If-the-sum-of-the-three-elements-is-divisible-by-3-then-the-number-of-subsets-that-canbe-made-is-x-Find

Question Number 187948 by horsebrand11 last updated on 24/Feb/23

Given a set H = {1, 2, 3, \dots, 300 . We will a

cre a te a subset of H consisting of

thre e elements . If the sum of the

thr e e elements is divisible by 3

then the number of subsets that

canbe made is x . Find the

remaind e r if x is divided by 100000

Answered by mr W last updated on 24/Feb/23

H_{1} = {1, 4, 7, . ., 298} w i t h 100 e l e m e n t s

H_{2} = {2, 5, 8, . ., 299} w i t h 100 e l e m e n t s

H_{3} = {3, 6, 9, . ., 300} w i t h 100 e l e m e n t s

s u c h t h a t t h e s u m o f 3 e l e m e n t s f r o m

H i s d i v i s i b l e b y 3, t h e r e a r e f o l l o w i n g

p o s s i b i l i t i e s :

1) a l l 3 e l e m e n t s a r e f r o m H_{3} o r H_{1} o r H_{2}

2) o n e e l e m e n t f r o m H_{1}, o n e f r o m H_{2}

a n d o n e f r o m H_{3}

t o t a l n u m b e r o f w a y s :

x = 3 \times C_{3}^{100} + C_{1}^{100} \times C_{1}^{100} \times C_{1}^{100} = 1 485 100

x m o d 100000 = 485 100

Commented by cortano12 last updated on 24/Feb/23

sir i think it = {3 C}_{3}^{100} + 100^{3}

it is correct ?

Commented by kapoorshah last updated on 24/Feb/23

w r o n g

T h e p o s s i b i l i t i e s :

(1) a l l 3 e l e m e n t s a r e f r o m H_{1}

(2) a l l 3 e l e m e n t s a r e f r o m H_{2}

(3) a l l 3 e l e m e n t s a r e f r o m H_{3}

(4) o n e e l e m e n t f r o m H_{1}, H_{2}, H_{3} r e s p e c t i v e l y

t o t a l n u m b e r o f w a y s :

x = 3 \times C_{3}^{100} + C_{1}^{100} \times C_{1}^{100} \times C_{1}^{100}

= 1 485 100

Commented by mr W last updated on 24/Feb/23

y e s, 3 \times C_{3}^{100} + 100^{3} i s c o r r e c t!

Commented by horsebrand11 last updated on 25/Feb/23

Y e s . .