Saf matematik, fizik, mantık (braingames.ru): ticari olmayan beyin oyunları - sayfa 58

Yeni yorum
 
DmitriyN :
Dolayısıyla: Tüm merdivenlerin açıkça tanımlanmış bir alt ve üst kısmı vardır.
Bu, merdivenlerin her zaman bir üst ve alt basamağa sahip olduğu anlamına gelmez. Merdivenlerin üst ve alt olduğunu söylüyor, yani. çevrilemezler. Onlar. merdivenin üst / alt kısmına göre ayna simetrik - aynı değildir.
 
Mathemat :

80 megaakıl, 10×8 dikdörtgen şeklinde düzenlenmiştir. Her uzunlamasına sırada en uzunu bulundu, aralarında köpekli mega zeka en düşük olanıydı. Sonra her enine sırada en alttakini buldular, aralarında şapkalı megamind en uzun olduğu ortaya çıktı. Soru şu ki, kim daha uzun: köpekli bir mega zeka mı yoksa şapkalı mı?

4ke'de olduğu gibi görünüyordu.

X >= Y >= Z --> X >= Z

 
Mathemat :

(5)

Megamind bir merdiven kullanarak evinin çatısına tırmanmak istiyor. Kilerde çok sayıda merdiven var ama ne yazık ki çoğunun yeterli basamağı yok. Arka arkaya iki basamak eksik olan merdivenler Megamind tarafından çıkılamaz. Tüm merdivenleri başlangıçta N basamaklıydı. Tüm merdivenlerin açıkça tanımlanmış bir alt ve üst kısmı vardır. Megamind'in tırmanması için kaç merdiven seçeneği var?

Tex, daha kolay. Fibonacci tavşanlarının dizisi çizildi.

F(1) = 2

F(2) = 3

F(N) = F(N-1)+F(N-2)

// Tekrarlamayan formül var mı bilmiyorum. Henüz doğru bulmadım.

 
TheXpert :

Elbette?

F(1) = 1

F(2) = 2

F(3) = 4

F(4) = 7

F(5) = 12

F(6) = 19

F(7) = 33 (???)

Emin.

Tek adımda 2 seçenekli (evet/hayır)

İki = üç seçenekli (her ikisi de birincisi olmadan, ikincisi olmadan)

vb.

Formülüm doğru.


Kommersant

 
MetaDriver :

Formülüm doğru.

Evet muhtemelen. Tüm merdiveni saymadım ve yaklaşık 6 için kaçırdım.
 

Özyinelemeli formül e, ama benim için o kadar basit değil. Ama sonuç ve çözümün kendisi aslında F(N+2) Fibonacci sayılarıdır. Geriye sadece doğru kanıtı vermek kalıyor. MD , formülünüzü nereden aldınız? Sadece küçük sayılar için seçenekleri mi sayıyorsunuz?

Formülün tam çıktısına sahibim. Ben beklerken.

 
TheXpert :

4ke'de olduğu gibi görünüyordu.

X >= Y >= Z --> X >= Z

Bunların ne tür buglar olduğunu açıklayabilir misiniz?
 
Mathemat :

Özyinelemeli formül e, ama benim için o kadar basit değil. Ama sonuç ve çözümün kendisi gerçekten Fibonacci sayıları F(N+2). Geriye sadece doğru kanıtı vermek kalıyor. MD , formülünüzü nereden aldınız? Sadece küçük sayılar için seçenekleri mi sayıyorsunuz?

Formülün tam çıktısına sahibim. Ben beklerken.

c(n), MM'nin çıkamayacağı n basamaklı merdiven sayısı olsun. Aşağıdaki seçenekleri göz önünde bulundurun:

on

100

İşte üç dizi merdivenin alt basamakları, 1 - bir basamak var, 0 - hayır. Açıkçası, n >= 2 için

c(n) = c(n-1) + c(n-2) + 2^(n-2), c(0) = 0, c(1) = 0 (1) olduğu açıktır.

Çıkılabilecek toplam merdiven sayısı şu formülle ifade edilir: 2^n - c(n) =? F(n+2)

Hadi kanıtlayalım. işlevi tanımlayın

f(n+2) = 2^n - c(n); f(2) = 1'i hesaplayın, f(3) = 2, karşılık gelen Fibonacci sayılarıyla aynıdır. (2)

n > 1 için, c(n) değerini (2)'den (1)'e değiştiririz, şunu elde ederiz:

2^n - f(n+2) = 2^(n-1) - f(n+1) + 2^(n-2) - f(n) + 2^(n-2), ikinin kuvvetleri iptal edin, şunu elde ederiz:

f(n+2) = f(n+1) + f(n), Hesaplanan değerleri dikkate alarak f(2) = F(2) = 1, f(3) = F(3) = 2 f(n+2) = F(n+2) olduğu açıktır.

 

Bu arada, farklı bir çözümüm var (ikinin gücü yok):

N >= 2 olduğunu varsayıyoruz. Merdiveni 1. ve 2. basamaklar arasında (daha doğrusu onlar için olan yerler arasında) keselim. Üstte, basamaklar için N-1 yerleri olan, altta - tek bir yeri olan küçük bir merdiven olacak. Her ikisinin de doğru olduğu garanti edilir, ancak bazı adımlar genellikle eksik olacaktır.

MM tırmanabiliyorsa merdivene doğru diyoruz. Merdivendeki potansiyel adımların sayısına, sırası denir.

Kolaylık olması için, aşağıdaki gösterimi sunuyoruz: n dereceli ve eksik alt basamaklı normal merdiven sayısı q(n; yanlış) olarak ve alt basamak mevcutken - q(n; doğru) olarak gösterilecektir. n düzeyindeki tüm normal merdivenlerin sayısı q(n) olarak gösterilecektir.

İki durum vardır:

1. Üst merdivenin alt basamağı vardır. O zaman N düzeyindeki toplam "bileşik" merdiven sayısı q(N-1; true) * 2'ye eşittir, çünkü 1. sıradaki normal merdiven sayısı 2'dir.

Öte yandan, açıkçası, q(N-1; doğru) = q(N-2). Bu nedenle, bu durum için toplam doğru seçenek sayısı 2*q(N-2) olacaktır.

2. Üst merdivenin alt basamağı yoktur. N düzeyindeki toplam merdiven sayısı q(N-1; false) * 1'dir, çünkü bileşik merdivenin doğru olması için 1. sıradaki alt merdivenin bir basamağı olmalıdır.

Öte yandan, q(N-1; yanlış) = q(N-2; doğru) = q(N-3). Bu nedenle, toplam doğru seçenek sayısı q(N-3)'tür.

Bu nedenle, yineleme bağıntısına sahibiz:

q(N) = 2*q(N-2) + q(N-3).

Doğrusaldır ve har. bunun denklemi:

z^3 - 2*z - 1 = 0

Açıkça faktörlere ayrılıyor:

(z + 1) * (z^2 - z - 1) = 0.

Dolayısıyla kökler z_1 = ( 1 + sqrt(5) ) / 2 = fi, z_2 = 1 - fi, z_3 = -1'dir.

Denklemin genel çözümü doğrusal bir kombinasyondur.

q(n) = C_1*z_1^n + C_2*z_2^n + C_3*z_3^n (***).

İlk birkaç seçenek için manuel hesaplama, aşağıdaki seçenek sayısını verir - Fibonacci sayıları (F_0 = 0, F_1 =1):

q(1) = 2 = F_3,
q(2) = 3 = F_4,
q(3) = 5 = F_5,
q(4) = 8 = F_6,
q(5) = 13 = F_7, vb.

Desen bariz. (***) içinde değiştirin:

F_3 = C_1*z_1 + C_2*z_2 - C_3 (***).

F_4 = C_1*z_1^2 + C_2*z_2^2 + C_3 (***).

F_5 = C_1*z_1^3 + C_2*z_2^3 - C_3 (***).

İlk olarak, bu üç denklemden k-you C_i'nin benzersiz bir şekilde belirlendiğini not ediyoruz (sistemin ana belirleyicisi neredeyse sıfıra eşit olmayan Vandermonde belirleyicisidir). Öte yandan, C_1 = 1/sqrt(5) = -C_2 ve C_3 = 0 ise tam anlamıyla Fibonacci sayıları elde edilir.

Dolayısıyla cevap: N dereceli normal merdiven sayısı F_{N+2}'ye eşittir.
 
Mathemat :

Bu arada, farklı bir çözümüm var (ikinin gücü yok):

Fibonacci için aynı özyinelemeli bağıntı doğrudur: q(N) = 2*q(N-2) + q(N-3).

Dolayısıyla serinin üst üste gelmesi için serinin ardışık üç değerinin tesadüf olduğunu ispatlamak yeterliydi.

1...515253545556575859606162636465...229
Yeni yorum