mateforum.ro Forum Index mateforum.ro

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Generali

 
Post new topic   Reply to topic    mateforum.ro Forum Index -> Alte domenii -> Teoria jocurilor, economie si stiinte sociale
View previous topic :: View next topic  
Author Message
Ciprian Oprisa
Pitagora


Joined: 19 Feb 2008
Posts: 55
Location: Lyon sau Cluj sau Baia de Cris

PostPosted: Mon Sep 22, 2008 8:07 pm    Post subject: Generali Reply with quote

Din Consiliul Suprem de Aparare a Tarii fac parte 10 generali. Pentru a lansa o racheta, e nevoie sa se puna de acord cel putin 3 dintre acestia. Pentru asta, racheta are un cod de lansare, format din 3 numere. Ce informatii trebuie sa li se dea generalilor, astfel incat oricare 3, punand cap la cap informatiile, sa poata afla codul de lansare, dar oricare 2 sa nu poata?
_________________
Un lucru este ceea ce este, nu ceea ce pare a fi.
Back to top
View user's profile Send private message Yahoo Messenger
Liviu Paunescu
Pitagora


Joined: 26 Sep 2007
Posts: 85

PostPosted: Mon Sep 22, 2008 10:21 pm    Post subject: Reply with quote

E o problema de tip Kvant. Totusi ceva in enunt e gresit, sau nu il inteleg eu. Codul trebuie sa fie format din mai multe numere, nu doar 3. Daca fiecare general stie sau nu un numar, nu avem decat 8 submultimi ale unei multimi cu 3 elemente. Deci vor exista 2 generali care stiu acelasi lucru, ori asta e imposibil. Doi nu se pot decide, deci al treilea trebuie sa vina cu informatie in plus.
_________________
Mesajul Depeche Mode pentru matematicieni:
"You'll see your problems multiplied
If you continually decide
To faithfully pursue
The policy of truth"
Back to top
View user's profile Send private message
Laurian Filip
Site Admin


Joined: 25 Nov 2007
Posts: 469
Location: Bucuresti

PostPosted: Mon Sep 22, 2008 10:38 pm    Post subject: Reply with quote

fiecare general va stii \lbrace x_i,y_i,x_i,z_i,e_i} si ca
x_ia+y_ib+z_ic=e_i

cu conditia ca pentru oricare i si j diferite identitatea \frac{x_i}{x_j}=\frac{y_i}{y_j}=\frac{z_i}{z_j} sa fie falsa

evident a,b,c fiind cele 3 numere.
_________________
Bac Mat: Formule bacalaureat matematica
Triangle Solver: Rezolva orice triunghi
Gaseste Scrabble: Castiga la jocul cuvintelor
Resigilate PCG: Top oferte desigilate pcg + istoric pret
Back to top
View user's profile Send private message Visit poster's website
Liviu Paunescu
Pitagora


Joined: 26 Sep 2007
Posts: 85

PostPosted: Tue Sep 23, 2008 12:07 pm    Post subject: Reply with quote

Da superb. Nu intelesesem eu enuntul.
_________________
Mesajul Depeche Mode pentru matematicieni:
"You'll see your problems multiplied
If you continually decide
To faithfully pursue
The policy of truth"
Back to top
View user's profile Send private message
andreutzalove



Joined: 21 Feb 2011
Posts: 1

PostPosted: Tue Feb 22, 2011 4:59 pm    Post subject: Reply with quote

marfa jocul Very Happy
Back to top
View user's profile Send private message
lasamasatelas
Pitagora


Joined: 16 Nov 2007
Posts: 70

PostPosted: Tue Feb 22, 2011 8:38 pm    Post subject: Reply with quote

Conditia
\frac{x_i}{x_j}=\frac{y_i}{y_j}=\frac{z_i}{z_j}
nu e suficienta. Conditia e ca pt. oricare 3 indici diferiti i,j,k matricea 3\times 3 care e formata din liniile (x_i,y_i,z_i), (x_j,y_j,z_j) si (x_k,y_k,z_k) sa aibe determinant nenul. In principiu nu e greu dar ce faci daca ai 1000 de generali si vrei ca racheta sa poata fi lansata cand 100 din ei sunt de acorrd. Atunci fiecare dintre cei 1000 de generali trebuie sa prineasca un sir de 100 de numere astfel incat oricum am lua 100 de generali matricea 100\times 100 formata din linii continand sirurile de numere primite de cei 100 de generali sa fie inversabila. E vorba de C_{1000}^{100} matrici, un numar imens. Sa zicem ca dam fiecarui general niste numere foarte mari luate la intamplare. Atunci probabilitatea ca determinantii matricile acelea sa fie inversabila e f. mare si nu mai facem verificarea. Dara daca se ajunge sa fie nevoie sa fie folosit sistemul atunci trebuie sa fie rezolvat un sistem de 100 de ecuatii cu 100 de necunoscute, ceeea ce presupune multa munca.

Acum cativa ani la o conferinta vorbeam cu un matematician care se ocupa de teoria codurilor si mi-a spus de niste trucuri f. simpatice din domeniu. Unul se referea exact la problema asta. Vrem sa facem astfel incat o informatie sa poata fi accesata doar atunci cand n oameni sunt de acord. Ideea e sa informatia sa fie coeficientii unui polinom de grad n-1, sa-i spunem f(X). Daca avem m generali atunci informatia pe care o dam generalului i este valoarea lui f(i). Daca generalii i_1,\ldots,i_n se pun de acord sa lanseze racheta ei pot determina polinomul din valorile f(i_1),\ldots,f(i_n) folosind formula de interpolare a lui Lagrange. Sunt necesare cam 2,5\, n^2 inmultiri, 3,5\, n^2 adunari/scaderi si n impartiri.

Pentru a evita calculele cu fractii si numere mari nu se ia f\in{\mathbb Z}[X], ci f\in{\mathbb Z}_p[X] unde p e un numar prim mare.

EDIT
@admin

Dati-i un ban user-ului (spammer-ului) andreutzalove. (Ce-i drept, fara el nu dadeam de topicul asta.)
_________________
Nicu Beli

"Quapropter bono christiano, sive mathematici, sive quilibet impie divinantium, maxime dicentes vera, cavendi sunt, ne consortio daemoniorum animam deceptam, pacto quodam societatis irretiant."
(Sf. Augustin, 354-430)


Last edited by lasamasatelas on Wed Feb 23, 2011 11:12 am; edited 2 times in total
Back to top
View user's profile Send private message Visit poster's website
Laurian Filip
Site Admin


Joined: 25 Nov 2007
Posts: 469
Location: Bucuresti

PostPosted: Wed Feb 23, 2011 12:35 am    Post subject: Reply with quote

done.
_________________
Bac Mat: Formule bacalaureat matematica
Triangle Solver: Rezolva orice triunghi
Gaseste Scrabble: Castiga la jocul cuvintelor
Resigilate PCG: Top oferte desigilate pcg + istoric pret
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    mateforum.ro Forum Index -> Alte domenii -> Teoria jocurilor, economie si stiinte sociale All times are GMT + 2 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum



Powered by phpBB © 2001, 2005 phpBB Group