Math, asked by saurabhbhalla1390, 1 year ago

Number of ways to choose 3 integers such that their sum is multiple of 4

Answers

Answered by Blaezii
0

Answer:

Step-by-step explanation:

Three integers are selected from the integers 1 to 1000. In how many ways integers can be selected such that their sum is divisible by 4?

There are four possible answers, depending on:

Do you mean three distinct integers, or can there be repeats?

Do you care about order? That is, is 1+2+5 different from 2+1+5?

Let [k] represent the 250 numbers from 1…1000 which have a remainder of k when divided by 4; that is,

[1]={1,5,9,…,997}

[2]={2,6,10,…,998}

[3]={3,7,11,…,999}

[0]={4,8,12,…,1000}

In order for three integers to have a sum divisible by 4, we must have one of the following:

[0] + [0] + [0] — that is, all three come from [0]

[0] + [2] + [2] … or [2] + [0] + [2], or [2] + [2] + [0] (if order matters)

[1] + [1] + [2] … 3 distinct orders, if order matters

[2] + [3] + [3] … 3 distinct orders, if order matters

[0] + [1] + [3] … 6 distinct orders, if order matters

The middle three cases are essentially identical (two numbers from one set, and one from another), so in the computations below, we have multiplied those expressions by 3.

So, here are three of the four possible answers (I have only done minimal checking of my reasoning and computation, so don’t take these numbers as certain):

no repeats, order unimportant:

(2503)+3⋅(2501)(2502)+(2501)(2501)(2501)=41,541,750

no repeats, order important:

(2503)⋅3!+3⋅3(2501)(2502)⋅2!+6(2501)(2501)(2501)=249,250,500

repeats allowed, order important:

2503(1+3⋅3+6)=250,000,000

Note that the third answer is exactly 25% of the 10003 possible ordered triples (A,B,C), which makes sense.

The fourth case (repeats allowed, order unimportant) is a messier computation, because it requires that we consider separately (for example) 4+4+4, 4+4+8, 4+8+12, all of which fall in the “[0]+[0]+[0]” case.

EDIT: I initially left the fourth case unanswered, but (I think) there are 41,791,750 ways to select three numbers in this case. Details:

[0]+[0]+[0][0]+[2]+[2][1]+[1]+[2][2]+[3]+[3]⎫⎭⎬⎪⎪[0]+[1]+[3]all the same250one pair2502one of each2503+ all different+ (2503)+ all different+ 250(2502)+ one pair+ 250⋅249=2,635,500=7,843,750=15,625,000

Then compute 2,635,500+3⋅7,843,750+15,625,000=41,791,750.

Similar questions