[SPAM] [obm-l] segunda fase - nível universitário 2007

[Rodrigo Cientista <rodrigocientista@xxxxxxxxxxxx>]

SPAM: -------------------- Start SpamAssassin results ----------------------
SPAM: This mail is probably spam.  The original message has been altered
SPAM: so you can recognise or block similar unwanted mail in future.
SPAM: See http://spamassassin.org/tag/ for more details.
SPAM: 
SPAM: Content analysis details:   (7.40 hits, 5 required)
SPAM: X_MAILING_LIST     (-0.3 points) Found a X-Mailing-List header
SPAM: SPAM_PHRASE_00_01  (0.8 points)  BODY: Spam phrases score is 00 to 01 (low)
SPAM:                    [score: 0]
SPAM: FORGED_YAHOO_RCVD  (1.4 points)  'From' yahoo.com does not match 'Received' headers
SPAM: RCVD_IN_ORBS       (2.2 points)  RBL: Received via a relay in orbs.dorkslayers.com
SPAM:                    [RBL check: found 93.38.190.206.orbs.dorkslayers.com., type: 68.178.232.99]
SPAM: RCVD_IN_OSIRUSOFT_COM (0.4 points)  RBL: Received via a relay in relays.osirusoft.com
SPAM:                    [RBL check: found 93.38.190.206.relays.osirusoft.com.]
SPAM: X_OSIRU_OPEN_RELAY (2.7 points)  RBL: DNSBL: sender is Confirmed Open Relay
SPAM: AWL                (0.2 points)  AWL: Auto-whitelist adjustment
SPAM: 
SPAM: -------------------- End of SpamAssassin results ---------------------

PROBLEMA 2:
Dado um inteiro positivo n, mostre que existe um inteiro positivo N com a seguinte propriedade: se A é um subconjunto de {1,2,...,N}  com pelo menos N/2 elementos, então existe um inteiro positivo m<= N - n   tal que  |A interseção com {m+1, m+2,..., m+k}|>=k/2
 
para todo k = 1, 2, …, n.

**************************************************************************************************************************
(gostaria de comentários sobre esta demonstração, falhas, se conhecem alguma demonstração pra esse problema, pois ainda não tem o gabarito)

suponha existir x > N - n tal que  |A interseção com {x+1, x+2,..., x+k}|>=k/2

como x + n > N, pelo menos um elemento de  {x+1, x+2,..., x+k} será maior que qualquer elemento de A; escolhendo-se um n = 1, a afirmação acima é falsa

assim, se  |A interseção com {m+1, m+2,..., m+k}|>=k/2 ==> existe m <= N - n

chamemos S = {m+1, m+2,..., m+k}

m + n <= N ==> m + k <= N para todo k = 1, 2, …, n ==>

 ==> S é subconjunto de {1,2,...,N}, ou é o próprio conjunto {1,2,...,N} na hipótese em que  N = n

quando N = n é trivial que |A interseção com {m+1, m+2,..., m+k}|>=k/2 (= k/2 na verdade)

suponha N > n ==> N/2 > n/2 ==> |{1,2,...,N}| > |S| ==> |A| > |S|/2 = n/2

como S está contido em {1,2,...,N} ==> é sempre possível tomar-se um subconjunto A de {1,2,...,N} tal que S/2 esteja contido em A


      Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento!
http://br.mail.yahoo.com/

=========================================================================
Instru�s para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================