تبلیغات
..::IRANIAN MATH OLYMPIAD::.. - چند سری سوالات ترکیبیات
 
درباره وبلاگ


این وبلاگ پاتوق همه شیفتگان ریاضی است..

مدیر وبلاگ : سیامک کریمی
نویسندگان
صفحات جانبی
نظرسنجی
چند عدد طبیعی n وجود دارد که مجموع !1+!2+...+!n مربع کامل شود؟









آمار وبلاگ
  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :
..::IRANIAN MATH OLYMPIAD::..
هر کس ریا ضی نمی داند وارد نشود؟؟؟
صفحه نخست             تماس با مدیر           پست الکترونیک               RSS                  ATOM
یکشنبه 9 خرداد 1389 :: نویسنده : سیامک کریمی

با سلام با عرض پوزش به دلیل مدتی تاخیر

چند تا سوال از ترکیبیات براتون گذاشتم حل کنید اگر مشکلی داشتید در قسمت نظرات بنویسید

 

 

منتظر انتفادات و نظراتتان هستم.   سیامک

 البته سوالات به زبان انگلیسیند ولی میتونید بفهمید.

1. [5] Given sets A and B, each of cardinality, how many functions map A in a one-to-one fashion onto B?

2. [5] a. Given the set of r symbols , how many different strings of length  exist?

 [5]b. Given the set of r symbols , how many different strings of length  exist that contain at least one ?

3. [10] Present a combinatorial argument that for all positive integers x and y

.

(Hint: Consider sequences drawn from the union of distinct sets A and B of cardinalities x and y, respectively.)

4. [5] Given m a’s, n b’s, and p c’s,  how many distinct sequences are there that employ each of the  symbols exactly once?

5. [5] If four six-sided dice are thrown , how many different configurations (ignoring order) are possible? (Understand: the configuration {2, 2, 3, 4} is the same as the configuration {2, 3, 2, 4 } but different from {2, 3, 3, 4})

6. [10] A pair of six-sided dice are thrown r times. (We ignore order in the pair but not in the sequence. Thus the sequence beginning (1,2), (2,6), (1,3),... is the same as the sequence (2,1), (2,6), (1,3),... but different from the sequence (2,6), (1,2), (1,3),...). How many such sequences have each of (1,1), (2,2), ..., and (6,6) appearing at least once within the sequence?  (Hint: First figure how many configurations can be displayed in a single throw of the pair. Second, figure how many total sequences of length r there are, without considering the requirement for the 6 certain pairs. Lastly, let  = the set of such sequences avoiding (i,i) and apply the inclusion/exclusion principle.)

7. [5] a. Suppose k numbers are drawn from {1, 2, ..., n} allowing repetitions. Considering order to be relevant, how many such strings are there?

[5] b. Now assume each of the different strings in part a. is equally likely. What is the probability that the maximum of the k numbers is greater than or equal to r, where ?

8. [5] Consider the following tables of probabilities for getting certain grades in a course and being in the freshman class. What is the probability of getting an A given that a student is a freshman?

Freshman

Non-Freshman

A

.3

.2

Less than A

.4

.1

9. [10] Suppose a message consists of 0’s and 1’s being transmitted with equal likelihood until five 1’s have been transmitted (i.e., the message terminates with the fifth 1). Give an expression for the expected value of the number of bits in the message? (Don’t waste time trying to simplify the expression.)

1. [5] Given set A of cardinality  and set B, of cardinality, how many functions map A in a one-to-one fashion into B?

2. [5] a. Given the set of r symbols , how many different strings of length  exist?

[5]b. Given the set of r symbols , how many different strings of length  exist that contain at least two ’s?

3. [10] Present a combinatorial argument that for all positive integers :

.

4. [5] Given m a’s, n b’s, p c’s and q d’s,  how many distinct sequences are there that employ each of the + q symbols exactly once?

5. Consider sequences of the form <>, where the . For fixed positive values of r and n, how many such sequences are there satisfying

6. [5] a. Suppose  and k numbers are drawn from {1, 2, ..., n} without allowing repetitions.  Considering order to be relevant, how many such strings are there?

[5] b. Now assume each of the different strings in part a. is equally likely. What is the probability that the minimum of the k numbers is less than or equal to r, where ?

7. [5] Consider the following tables of probabilities for getting certain scores on an exam and being a CS major or not. Is the event of getting at lease a score of 80 independent of the event that the student is a CS major?

CS Major

non-CS Major

90 to 100

.08

.02

80 to 89

.17

.06

70 to 79

.28

.10

60 to 69

.14

.08

0 to 59

.08

.02

8. [10] Suppose a message consists of a total of n 0’s and 1’s being transmitted with equal likelihood.  Give an expression for the expected value of the number of 1’s minus the number of 0’s in the message? (Don’t waste time trying to simplify the expression.)

1. [5] a. Suppose all people either have one word names (e.g. "Cher"), two word names (e.g., "Jack Sprat") or three word names (e.g. "Richard Milhous Nixon"). How many different sets of initials can people have?

 [5]b. Suppose all 10 digit telephone numbers obeyed these rules:

            the first digit cannot be 1.

            The second digit must be 0 or 1

            the other 8 digits can be and decimal digit.

How many such 10 digit telephone numbers are there?

2. [5] a. How many permutations of a, b, c, d, e, and f have b to the left of c?

 [5]b. How many permutations of a, b, c, d, e, and f have b to the left of c and e to the left of f?

3. [5] a. Present a combinatorial argument that for all positive integers n, a, and b(>a):

.

[5] b. Present a combinatorial argument that for all positive integers n:

4. [10] An alphabet A contains exactly n characters. A message consists of an ordered array of elements of A (permitting repetitions)?  If for each position in the message each character is equally likely, what is the probability that a message of length n does not contain all n characters.

5. [10] Suppose m are cards are to be drawn from a 52 card deck with repetition possible. What is the probability that cards 1, 2, …, m-1 are not hearts but card m is a heart?

6. [10] Let E be a set of equally likely events and A and B be subsets of E.  Show that

7. [5] Consider the following tables of probabilities for getting certain scores on an exam and being a CS major or not. Is the event of getting at lease a score of 70 independent of the event that the student is a CS major?

CS Major

non-CS Major

90 to 100

.08

.02

80 to 89

.17

.04

70 to 79

.28

.12

60 to 69

.14

.08

0 to 59

.08

.02

8. [10] Suppose a message consists of a total of n 0’s and 1’s being transmitted with equal likelihood.  What is the expected number of 0's?

1. [10]. Given set A of cardinality  and set B, of cardinality, how many functions mapping A into B are not one-to-one?

2. [10] For , determine the number of strings of a's and b's of length n that either begin with the string ab or end with the string ba or both. (Do not ignore the cases of n = 2, and n = 3.)

3. a. [10] Assuming , Let and . How many strings using each of these symbols exactly once have the symbols of A and B occurring in the order given (i.e. in the string  must occur to the left of  if  and similarly for B)?

b. [10] How many strings using each of these symbols exactly once have the symbols of just A occurring in the order given but not necessarily B?

4. [10] Using a combinatorial argument, prove that for :

5. a.[5] For , assume all strings of length n from the set {a, b, c} (allowing repetition) are equally likely. What is the probability that such a string has no a?

b. [5] What is the probability that such a string has no b given that it has no a?

6. [10] Given non-negative integers , , , and , how many distinct strings of length are there that have exactly  1's,  2's,  3's, and 4's?

7. [10] How many triples  of non-negative integers , , and  exist that satisfy . (Hint: Think about balls and bins.)

8. [10] For , assume all strings of length n from the set {a, b, c} (allowing repetition) are equally likely. What is the expected number of c's.

1. [10] For consider bit strings of length n. How many such strings begin with the substring 111, end with the substring 111, or both? (Do not ignore n = 3, 4, and 5.)

2. a. [10] Present a combinatorial argument that for all positive values of n:

 b. [10] Present a combinatorial argument that for all m and n satisfying , , and :

(Hint: Consider , where , , and .)

3. a. [10] For , how many decimal numbers between 1 and  contain no 5's or 7's.?

 b. [10] For , how many decimal numbers between 1 and  contain at most one 5 and one 7?

4. [10] For ,  how many ways can you find ordered triples  so that i, j, and k are non-negative and their sum is n? (Hint: Consider balls and bins.)

5. [10] For , assume all strings of n digits from are equally likely. What is the expected number of 9's in such a string?

6. [10] For , what is the probability that a string of length n of a's b's , c's, and d's has three or more a's (assuming all such strings are equally likely)?

7. [10] Consider two cards drawn from a 52 card deck and assume all such draws are equally likely.  Is the event that a heart is drawn as the first card independent of the event that a spade is drawn of the second card?

1. [10] For consider a set A of cardinality n. How many subsets of A are of cardinality less than or equal to 3?

2. a. [10] Present a combinatorial argument that for all n and k satisfying  and :

 b. [10] Present a combinatorial argument that for all positive values of n:

(Hint: Consider Let k be the position of the first 1 in a bit string.)

3. a. [10] For , consider strings of length n from the set of characters {a, b, c, d, e, f}allowing repetition. How many such strings at most one a and one b?

   b. [10] For , how many decimal numbers between 1 and  contain at most one 5 and one 7?

4. [10] For , in how many ways can you place m balls into n boxes so that every box has at least one ball?

5. [10] For , assume all strings of n digits from are equally likely. What is the expected number of 9's in such a string?

6. [10] For , what is the probability that a string of length n of a's b's , c's, and d's has three or more a's (assuming all such strings are equally likely)?

7. [10] Consider two cards drawn from a 52 card deck and assume all such draws are equally likely.  Is the event that a heart is drawn as the first card independent of the event that a spade is drawn of the second card?

1. [5] Consider integers in the set {1, 2, 3, …, 1000}. How many are divisible by either 4 or 10?

2. a. [10] Present a combinatorial argument that for all :

 b. [10] Present a combinatorial argument that for all nonegative integers p, s, and n satisfying  

(Hint: Consider choosing two subsets.)

3.  [10] For , Let A = {1, 2, …, 2n}. How many subsets of A contain exactly even numbers and odd numbers?

4. [10] For , how many ordered triples of non-negative numbers satisfy ? (Hint: think about putting balls into bins.)

5. [10] For , assume all strings of n characters from are equally likely. What is the expected number of a's in such a string?

6. [10] Given a finite event space E (in which all events are equally likely) and subsets A and B of E, show that

.

7. [10] Consider a 52 card deck of cards from which the ace of spades is removed resulting in a 51 card deck. Further, consider two distinct cards drawn from the 51 card deck and assume all such unordered draws are equally likely.  Lastly consider the probability of the event that both cards are hearts. Is it more likely that both cards are hearts if it is given that both cards are face cards (i.e., Kings, Queens, or Jacks)?

8. [10] Let A be a set of cardinality p. Consider ordered strings of length m using the elements of A.  How many such strings have the mth  component a repetition of one of the preceding m-1? (Hint: Think about the complement and think about selecting the mth component first.)

1. [5] Suppose all rolls of a six-side die are equally likely.  What is the probability the roll is a six given that it is not one?

2. a. [10] Present a combinatorial argument that for all :

(Note: The summation begins with .)

b. [10] Present a combinatorial argument that for all integers k  and n satisfying

(Hint: Consider three special elements.)

3.  [10] How many distinct permutations are there of the letters in “mississippi”?

4. [10] A bin has 100 blue balls, 100 red balls, and 100 green.  How many different collections can I obtain using 100 of these balls?  (Balls of the same color are indistinguishable from one another but are distinguishable from balls of another color. A “collection” has no order to it.)

5. [10] Assume all strings of length five using characters from are equally likely. What is the probability that there is a substring  in the string?

6. [10] Suppose a number k from {1, 2, …, 100} is to be drawn and that all numbers are equally likely.  Let A be the event k is a power of two.  Let B be the event k is an integer multiple of four.  Prove either that the events A and B are statistically independent or that they are statistically dependent.

7. [10] For , consider strings of length n containing 0’s and 1’s but ending in a 1.  Assume all such strings are equally likely.  What is the expected number of 1’s in such a string?

8. [10] For , how many strings of length n employing the characters {a,b,c} have at least one a?

1. [5] For , how many subsets of size 3 from  are there that either contain  or  (or both)?

2. [10] Given a set  of  characters, for , consider strings of length  using any of the characters of .  How many such strings begin and end with the same character?

3. [10] Present a combinatorial argument that for all positive integers  and , satisfying :

.

(Hint: Consider selecting from two sets.)

b. [10] Present a combinatorial argument that for all positive integers n :

(Note: Be very specific about the roles of  and .)

4. [10] How many distinct permutations are there of the digits in 1121231234?

5. [10] Given , in how many ways can  identical balls be placed into  distinct bins such that each bin contains at least one ball? (Hint: Consider strings with balls and special dividers.)

6. [10] For , consider strings of length  0’s and 1’s.  Assuming all such strings are equally likely, what is the probability that such a string has an equal number of 0’s and 1’s?

7. a. [10] For consider strings of length using elements of . Assume all such strings are equally likely.  What is the probability that a string has exactly two a’s?

    b. [5] What is the probability that such a string has exactly three b’s given that it has exactly two a’s?





نوع مطلب : سوالات هفتگی، 
برچسب ها :
لینک های مرتبط :


شنبه 25 شهریور 1396 04:45 ق.ظ
After exploring a number of the articles on your website, I
truly appreciate your way of writing a blog. I saved it to my bookmark webpage list and will be
checking back soon. Take a look at my website
as well and tell me how you feel.
شنبه 18 شهریور 1396 11:04 ق.ظ
برای همه چی، برای من واقعا خوشحالم که این وبسایت را ببینم، شامل اطلاعات مفید می شود.
جمعه 17 شهریور 1396 10:31 ب.ظ
شما مطمئنا می توانید تخصص خود را در مقاله ای که می نویسید مشاهده کنید.
عرصه امیدوار است برای نویسندگان پرشور مانند شما که نترسید
می گویند چطور باور دارند همیشه از قلب خود پیروی کنی
جمعه 17 شهریور 1396 07:01 ب.ظ
بسیار! این یک پست فوق العاده است.
متشکرم برای تهیه این اطلاعات
جمعه 17 شهریور 1396 02:16 ق.ظ
می توانم بگویم که راحتی کشف کسی که واقعا می داند چه چیزی در مورد شبکه صحبت می کند.

شما قطعا متوجه می شوید که چگونه یک مسئله را به نور تبدیل کنید
و مهم آن است مردم بیشتر باید بخوانند
این و درک این قسمت از داستان شما. من شگفت زده شدم که تو
با توجه به اینکه شما مطمئنا این را دارید، محبوبیت بیشتری ندارید
هدیه.
شنبه 4 شهریور 1396 10:02 ب.ظ
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my
blog that automatically tweet my newest twitter updates.

I've been looking for a plug-in like this for quite some time
and was hoping maybe you would have some experience with something like this.

Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your new updates.
دوشنبه 16 مرداد 1396 08:55 ب.ظ
Does your website have a contact page? I'm having trouble locating it but, I'd like
to shoot you an e-mail. I've got some creative ideas for your
blog you might be interested in hearing. Either way, great site and
I look forward to seeing it expand over time.
پنجشنبه 7 اردیبهشت 1396 08:10 ب.ظ
If some one desires expert view concerning running a blog then i recommend him/her to pay a visit this web
site, Keep up the nice job.
سه شنبه 29 فروردین 1396 06:10 ق.ظ
If you are going for finest contents like I do, simply pay a quick visit this
web page all the time as it offers quality contents, thanks
جمعه 27 تیر 1393 07:17 ب.ظ
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر