سوال استقرا با طعم جدول

rza · 1389/6/5

ثابت كنيد جدولي 2[SUP]n[/SUP]*2[SUP]n [/SUP]با اعداد 1,0وجود دارد به طوري كه هر دو سطر اين جدول دقيقا در2[SUP]n-1[/SUP] مرتبه اختلاف داشته باشند. مثلا جدول زير اين ويژگي را دارد

[TABLE][TR][TD]

1<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com

ffice

ffice" /><o

></o

>[/TD][TD]
1<o

></o

>[/TD][TD]
1<o

></o

>[/TD][TD]
1<o

></o

>[/TD][/TR][TR][TD]
0<o

></o

>[/TD][TD]
1<o

></o

>[/TD][TD]
0<o

></o

>[/TD][TD]
1<o

></o

>[/TD][/TR][TR][TD]
0<o

></o

>[/TD][TD]
0<o

></o

>[/TD][TD]
1<o

></o

>[/TD][TD]
1<o

></o

>[/TD][/TR][TR][TD]
1<o

></o

>[/TD][TD]
0<o

></o

>[/TD][TD]
0<o

></o

>[/TD][TD]
1<o

></o

>[/TD][/TR][/TABLE]

SABB · 1389/6/6

اگه جدول G از 1 و 0 ساخته شده باشد، (F(G رو جدولی از 0 و 1 با هموناندازه G در نظر میگیریم که درایه هاش نقیض شدن (1 ها 0 و 0 ها 1 شدن). پابه استقرا برای n==0 که بدیهیه. فرض کنیم برای n درست باشه و جدول مطلوب G نام داشته باشه، اون موقع برای n+1 جدول زیر خاصیت مطلوب رو داره:

[center:a46acac5c8]G G
F(G) G[/center:a46acac5c8]
اثبات:
این که بدیهیه همه ی سطرهای 1 تا 2[SUP]n[/SUP] با همدیگه و همینطور همه ی سطرهای 2[SUP]n[/SUP]+1 تا آخر با همدیگه دقیقا تو 2[SUP]n[/SUP] تا مرتبه اختلاف دارن. حالا یه سطر مثل

$\100dpi \inline i\leq 2^n$

و یکی دیگه مثل

$\100dpi \inline j\geq 2^n+1$

رو در نظر میگیریم. میدونیم تعداد تفاوت های

$\100dpi \inline i$

و

$\100dpi \inline j$

برابر تعداد تفاوت های سطر

$\100dpi \inline i$

ام و

$\100dpi \inline j-2^n$

ام G به اضافه ی تعداد تفاوت های سطر

$\100dpi \inline i$

ام G و

$\100dpi \inline j-2^n$

ام (F(G هست. حالا باتوجه به اینکه اگه سطر

$\100dpi \inline i$

ام و

$\100dpi \inline j-2^n$

ام G با هم تو k مرتبه اختلاف داشته باشن، اونوقت سطر

$\100dpi \inline i$

ام G و

$\100dpi \inline j-2^n$

ام (F(G تو 2[SUP]n[/SUP]-k مرتبه اختلاف خواهند داشت؛ پس سطر

$\100dpi \inline i$

و

$\100dpi \inline j$

دقیقا در 2[SUP]n[/SUP]-k+k=2[SUP]n[/SUP] مرتبه با هم تفاوت دارند.

Goharshady · 1389/6/6

rza گفت

ثابت كنيد جدولي 2[SUP]n[/SUP]*2[SUP]n [/SUP]با اعداد 1,2 وجود دارد به طوري كه هر دو سطر اين جدول دقيقا در2[SUP]n-1[/SUP] مرتبه اختلاف داشته باشند. مثلا جدول زير اين ويژگي را دارد

[TABLE][TR][TD]

1<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com

ffice

ffice" /><o

></o

>[/TD][TD]
1<o

></o

>[/TD][TD]
1<o

></o

>[/TD][TD]
1<o

></o

>[/TD][/TR][TR][TD]
0<o

></o

>[/TD][TD]
1<o

></o

>[/TD][TD]
0<o

></o

>[/TD][TD]
1<o

></o

>[/TD][/TR][TR][TD]
0<o

></o

>[/TD][TD]
0<o

></o

>[/TD][TD]
1<o

></o

>[/TD][TD]
1<o

></o

>[/TD][/TR][TR][TD]
1<o

></o

>[/TD][TD]
0<o

></o

>[/TD][TD]
0<o

></o

>[/TD][TD]
1<o

></o

>[/TD][/TR][/TABLE]

این که با صفر و یک پر شده

rza · 1389/6/6

از
Goharshady تشكر مكنم اشتباه تايپي بوده.0و1

Goharshady · 1389/6/6

آقای رجبی هنوز با رسم های ما آشنا نیستند. الآن باید تکذیب می شد

Olympiad · 1389/6/6

Goharshady گفت

سوال استقرا با طعم جدول

rza

New Member

SABB

New Member

Goharshady

New Member

rza

New Member

Goharshady

New Member

Olympiad

New Member