Lottery

[nasi112]

Please don't solve my question. I just need some guidance.

You choose r of the first n positive integers, and a lottery chooses a random subset L of the same size. What is the probability that:

(a) L includes no consecutive integers?
(b) L includes exactly one pair of consecutive integers?
(c) the numbers in L are drawn in increasing order?
(d) your choice of numbers is the same as L?
(e) there are exactly k of your numbers matching members of L?

I don't understand the main sentence You choose r of the first n positive integers, and a lottery chooses a random subset L of the same size.

Can you give me three examples of r and L?

 

[blamocur]

For example: you pick 15 numbers between 1 and 100, and the lottery picks 15 numbers from the same range. Here [imath]r=15[/imath] and [imath]n=100[/imath]. Does this make sense?

 

[nasi112]

Thanks blamocur. I understood the main sentence.

For example: you pick 15 numbers between 1 and 100, and the lottery picks 15 numbers from the same range. Here [imath]r=15[/imath] and [imath]n=100[/imath]. Does this make sense?

Does this mean there are unlimited sets?

One set n = 5
{1,2,3,4,5}
one choice r = 3
01-{1,2,3}
02-{1,2,4}
03-{1,2,5}
04-{1,3,4}
05-{1,3,5}
06-{1,4,5}
07-{2,3,4}
08-{2,3,5}
09-{2,4,5}
10-{3,4,5}

There are 10 subsets only {1,3,5} contains no consecutive integers.

The probability is 1/10 = 0.1

Did I analyzed correctly?

That was only one case. If there are unlimited sets and choices, how I will find a pattern to write a general formula of probability?

 

[blamocur]

Does this mean there are unlimited sets?

I don't get this question.

Did I analyzed correctly?

Looks correct to me. Now, can you figure out a formula for the general case of arbitrary [imath]r[/imath] and [imath]n[/imath]? Without spending more time on this I don't know the answer

 

[Dr.Peterson]

If there are unlimited sets and choices, how I will find a pattern to write a general formula of probability?

Presumably you are asking only about part (a) so far, right?

How much have you learned about combinatorics? I think "stars and bars" might work for (a).

Where did this problem come from, that the first part would be so hard?

 

[blamocur]

Without spending more time on this I don't know the answer

After spending some time, I think I have a useful hint: subsets without consecutive numbers correspond to (unrestricted) subsets of the same size but from a smaller space.

 

[nasi112]

I don't get this question.

n = 5 gave one set {1,2,3,4,5}. n can have any positive integer, so I asked if this means there are unlimited sets. Does my question make sense?

Looks correct to me.

Thanks.

Now, can you figure out a formula for the general case of arbitrary [imath]r[/imath] and [imath]n[/imath]?

No.

Without spending more time on this I don't know the answer

It's O.K. I don't know the answer either.

After spending some time, I think I have a useful hint: subsets without consecutive numbers correspond to (unrestricted) subsets of the same size but from a smaller space.

It would be nice if you give me an example.

Presumably you are asking only about part (a) so far, right?

Yes I am trying to solve (a) at this moment.

How much have you learned about combinatorics?

I was good. I forgot. I am relearning again.

I think "stars and bars" might work for (a).

What is this?

Where did this problem come from, that the first part would be so hard?

This problem came from google. (a) through (d) I got it from coursehero. I found later part (e) in Chegg. I didn't know at first the question was missing part (e). By chance I found the same question in Chegg. They are paid websites, so I can't see the solution. Actually I don't want to see the solution because I want to practise to solve by myself.

Do you think first part is so hard, Doctor?

 

[blamocur]

n = 5 gave one set {1,2,3,4,5}. n can have any positive integer, so I asked if this means there are unlimited sets. Does my question make sense?

You mean there are no restrictions on 'n' ?

 

[blamocur]

It would be nice if you give me an example.

I didn't know about "stars and bars" mentioned by @Dr.Peterson, but my approach seems equivalent:
Given a subset [imath]S_1[/imath] of [imath]r[/imath] numbers satisfying (a) you can remove from the "big set" (of [imath]n[/imath] numbers\) [imath]r-1[/imath] numbers following each of the numbers in the subset [imath]S_1[/imath] except the last one. This will result in a subset [imath]S_2[/imath] of [imath]r[/imath] numbers from a set of [imath]n-r+1[/imath] numbers. Unless I am mistaken the correspondence between [imath]S_1[/imath]'s and [imath]S_2[/imath]'s is one-to-one, and thus the numbers of such subsets are equal.

P.S. To reduce ambiguity: if [imath]S_1 = \{x_1, x_2, ..., x_r\}[/imath] we have to remove [imath]\{x_1+1,\; x_2+1, ..., x_{r-1}+1\}[/imath].

 

[Dr.Peterson]

Do you think first part is so hard, Doctor?

Do you think it's easy?

I think some of the others are a little more straightforward.

Have you worked it out yet, either from the direct hint you were given, or perhaps by looking up "stars and bars", which was my intent, and trying to use that tool?

I'd definitely start by trying it with specific small numbers, but doing a calculation rather than listing possibilities as you did (since the former can be generalized to make a formula, while the latter can't). For example, with n=10 and r=3, you want to place 3 bars among 7 stars,

**|*|****|​

The bars represent the non-consecutive integers chosen, and the stars are the other integers; the bars have to be separated by stars to make them non-consecutive. Calculate how many ways this can be done for this example; then do the same for any n and r.