Matematici Concrete

Unitatea 0

1. Sa se gaseasca numarul de moduri de a aseza soti si a sotiilor lor in jurul unei mese rotunde astfel incat fiecare barbat sa aiba ca vecine, de o parte si de alta, doua femei dintre care nici una sa nu-i fie sotie.

Rezolvare :

Notez : numarul de moduri

numerele de ordine ale sotilor

numerele de ordine ale sotiilor

O bijectie de la multimea pe multimea defineste o asezare in modul urmator : asezam pe un loc oarecare la masa persoana cu numarul , la dreapta sa persoana cu numarul , la dreapta sa persoana 2, la dreapta ei persoana cu numarul , etc.

Pentru , notez cu multimea bijectiilor cu si pentru notez cu multimea bijectiilor cu , iar pentru , notez multimea bijectiilor cu .

O bijectie defineste o aranjare care raspunde cerintelor problemei daca si numai daca nu apartine nici uneia dintre multimile

Deci

.

dar .

Afirmatie:

Daca multimea contine numere, atunci daca nu contine doi intregi consecutive din sistemul si in caz contrar.

Demonstratie:

Daca contine doi intregi consecutivi in sistemul , fie si , atunci, daca exista o bijectie , aceasta implica si, deci, si, in acelasi timp, , deci nu este injectiva.

Daca contine intregii si , rezulta, din ca si : absurd ( o functie este unic definita pe orice element din domeniu ).

Asadar, daca contine doi intregi consecutivi din sistemul , deoarece pentru numerele si , avem o situatie asemanatoare celor de mai sus.

Daca nu contine doi intregi consecutivi in , implica faptul ca imaginile a elemente din multimea , sunt binedefinite, iar restul imaginilor celor elemente pot fi alese in moduri, astfel incat sa fie o bijectie a multimii pe multimea .

Conform teoremei lui Kaplansky, numarul multimilor cu elemente care nu contin doi intregi consecutive din sistemul este : .

Se obtine, deci, :

= .

Sau

; .

2. Sa se scrie un program pentru calculul numerelor lui Fibonacci.

program fibonacci;

uses crt;

var v:array[1..100] of integer;

n,k,i,a,b:integer;

begin

clrscr;

writeln('Introduceti numarul pana la care doriti sa se afiseze valori din sirul lui Fibonacci:n=');read(n);

a:=1;b:=1;

v[1]:=1;v[2]:=1;

k:=2;

while v[k]<=n do

begin

k:=k+1;

b:=a+b;

v[k]:=b;

k:=k+1;

a:=a+b;

v[k]:=a;

end;

for i:=1 to k-1 do

writeln(v[i]);

if n=v[k-1] then writeln('Numarul dat de dumneavoastra este in sirul lui Fibonacci!')

else writeln('Numarul dat de dumneavoastra nu este in sirul lui Fibonacci!');

readln;

readln;

end.

Sau

#include<stdio.h>

#include<conio.h>

#define Max 100

long int f[Max];

void genereaza_fibonacci(int n,int i)