رياضيات گسسته - سري اول

تذكر مهم:
در كليه سوالات علامت راديكال بصورت ( √ ) وعلامت تقسيم بصورت( مخرج/صورت ) وعلامت مميز بصورت( , ) وعلامت ضرب بصورت (*) مي باشد

1 – نمودار زير مربوط به گراف (G(V,E است :

الف) مجموعه رئوس و مجموعه يال هاي گراف را مشخص كنيد.
ب) دو دور به طول 5 در اين گراف بنويسيد
ج) دنباله درجه هاي رأس هاي اين گراف را به صورت يك دنباله نزولي بنويسيد.
الف){V={V1,V2,V3,V4,V5,V6
{E={V1V2,V1V6,V2V3,V2V6,V3V4,V4V5,V4V6,V5V6
ب) V1V2V3V4V6V1, V2V3V4V5V6V2
ج) 4,3,3,2,2,2

  2 – ثابت كنيد در هر درخت با p رأس و q يال داريم : p=q+1

اثبات به كمك استقرار روي مرتبه گراف انجام مي شود براي P=1 داريم. Q=0 چون 1=0+1 پس p=q+1 فرض كنيد قضيه در مورد هر درخت با (k (k≥1 رأس درست باشد ثابت مي كنيم در درخت از مرتبه K+1 تعداد يال ها k است . يك از رأس هاي درجه 1 و يال مار بر آن را حذف مي كنيم گرافي از مرتبه K به دست مي آيد چنين گرافي طبق فرض استقراء k-1 يال دارد. پس درخت مرتبه k+1 داراي K يال است.  

  3- الف) گراف كامل را تعريف كنيد
ب) تعداد يال هاي گراف كامل مرتبه p از تعداد يال هاي درخت مرتبه P، 10 واحد بيشتر است، p را پيدا كنيد.

الف) گراف از مرتبه P كه (p-1) منتظم باشد را گراف كامل مي گويند.
ب)q(kp)-q(Tp)=10 --> P(p-1)/2 – (p-1)=10 --> p2 – 3p -18 =0 --> p=6  

  4 – الف)‌ثابت كنيد حاصل ضرب سه عدد طبيعي متوالي بر 6 تقسيم پذير است.
ب) ثابت كنيد حاصل ضرب دو عدد زوج متوالي بر عدد 8 تقسيم پذير است.

الف) از سه عدد طبيعي متوالي يكي مضرب 3 است و هم چنين يكي مضرب 2 هست . پس حاصل ضرب آنها مضرب 2و3 است چون (2,3)=1 پس مضرب 6=3×2 مي باشد.

ب)
2k(2k+2)=4k(k+1)=8q
k(k+1)=2q  

  5 – ثابت كنيد بي نهايت عدد اول وجود دارند.

اثبات فرض كنيم تعداد آنها محدود باشد و مجموعه آن {p1,p2,….,pn} باشد قرار مي دهيم m=p1p2…pn+1 چون m مركب است پس مقسوم عليه اولي مثل pj دارد:
Pj|m , Pj|p1 ,…… pn --> pj | m – p1p2 ….. pn --> pj|1غير ممكن  

  6 – نشان دهيد اگر a,b)=1) آنگاه (a,a-b)

(a,b)=1 --> эm,n€Z:ma+nb=1 --> ma + nb - na + na =1 -->(m + n)a + (-n)(a-b) = 1 --> (a , a-b)=1  

  7 – پستخانه اي فقط تمبرهاي 60 ريالي و 90 ريالي براي فروش دارد. شخصي براي فرستادن يك بسته كه نياز به 870 ريال تمبر دارد از هر نوع تمبر چه تعداد بايد بخرد.(تمام حالات ممكن براي خريد تمبر نوشته شود)

60x + 90y = 870
(60 + 90) = 30,30|870
2x + 3y = 29 ---> x= 29-3y/2 = 14- y + (1-y)/2
Y0=1 ---> x0=13 ---> [ x=x0 + b/d k ، y = y0 – a/d k]
----> [x=13+3x ، y =1-2k]

  8 – فرض كنيد {A={1,2,3,4 براي هر يك از حالات زير گرافي رسم كنيد كه رابطه متناظر با آن :
الف) بازتابي و ترايايي باشد ولي متقارن نباشد.
ب) بازتابي باشد ولي متقارن و پادمتقارن و ترايايي نباشد.

الف.

ب.

  9 – فرض كنيد A يك مجموعه n عضوي، n € N و R يك رابطه روي آن با ماتريس متناظر M باشد نشان دهيد اگر R ترايايي باشد آنگاه (2) M << M

M = [ m ij ]   M ⁽²⁾ = [ m' ij ]   m' ij = m i1 Θ m 1j +˚ .... +˚ m in Θ m nj
m' ij = 1 ----> З k = m ik Θ m kj =1 -----> m ik = 1 , m kj = 1
m ik = 1 ----> ( ai , a k ) € R
m kj = 1 ----> ( a k , a j ) € R
R ترايايي -----> ( a i , a j ) € R  ----> m ij = 1  

  10 – چند عضو از مجموعه {A = { n € N : 1 ≤ n ≥ 4200 نه بر 7 بخش پذيراست و نه بر 5.

A1 = {a€A:y|a} ---> |A1| = 4200/7 = 600 |A| = 4200
A2 = {a€A:5|a} ---> |A| = 4200/5 =840
A1∩A2 = {a€A:5|a.y|a}={a€aA:35|a} ---> |A1∩A2|=4200/35=120
|A1A2|=|A1| + |A2| - | A1∩A2|=600+840-120=1320--->
|A1UA2|=|A|-|A1UA2|=4200-1320

  11 – يك فضاي نمونه اي متشكل از 4 برآمد a,b,c,d است، به شرط آنكه P({b,c,d})=2/3 و P({b})=1/4 مطلوبست است :
الف) ({p({a,c,d}|{b,c,d
ب) ({p({a})|{a,c,d

الف .
P ( { a , c , d } | { b , c , d } ) = P ( { a ,c ,d } ∩ { b , c ,d } )  /  P ( { b ,c ,d } ) = P ( { c , d } ) / P ( { b , c , d } ) = [ (2 / 3 ) - (1 / 4) ]  / ( 2 / 3 ) 

ب . P ( { a } | { a , c , d } ) = P ( { a } )   /  P ( { a ,c ,d } )  =  (1 / 3 )   /  ( 3 / 4 ) = 4 / 9     

  12 – دو ظرف همانند داريم. اولي شامل 3 مهره سفيد و 4 مهره قرمز و دومي شامل 5 مهره سفيد و 3 مهره قرمز است.
از ظرف اول 3 مهره و از ظرف دوم 2 مهره به تصادف خارج كرده و در ظرف جديدي قرار مي دهيم. اگر از ظرف جديد مهره اي به تصادف خارج كنيم:
الف) احتمال اينكه مهره سفيد باشد چقدر است؟
ب) اگر مهره خارج شده از ظرف جديد سفيد باشد احتمال اينكه از ظرف دوم باشد چقدر است؟

الف.
A مهره خارج شده از ظرف جديد سفيد باشد.
B1 مهره خارج شده از ظرف جديد مربوط به ظرف اول باشد.
B2 :‌مهره خارج شده از ظرف جديد مربوط به ظرف دوم باشد.

P _(A) = P _(A|B1) P _(B1) + P _(A|B2) P _(B2) = (3/7)(3/5) + (5/8)(2/5) = 71 / 140

ب. P _{(B2 | A)} = P _(A|B2) [ P _(B2)  /  P _(A)] = ( 5/8) [ (2/5) / (71/140) ]  

  13 – در ظرفي 1 مهره سفيد و 1 مهره سياه است. اگر از اين ظرف 3 مهره با جايگذاري خارج كنيم و متغير تصادفي X را : «تعداد مهره هاي سفيد خارج شده» تعريف كنيم:
الف) متغير تصادفي X چه مقادير مي تواند اختيار كند.
ب) تابع احتمال متغير تصادفي x را به دست آوريد.

X=0,1,2,3
{(S={(w,w,w),(w,w,B),(w,B,w),(B,w,w) (w,B,B),(B,w,B),(B,B,w),(B,B,B