Sexta-feira, 27 de Fevereiro de 2009

O Método de Hondt

Foi em finais de 1979. Já passaram, portanto, 29 anos. Eu tinha concorrido numa lista para vereador da Câmara Municipal de Castelo Branco e estava eleito com 3 137 votos . No entanto, cerca de uma semana depois das eleições é feita a assembleia geral de apuramento dos votos, presidida por um juiz e onde são conferidos todos os documentos respeitantes às mesas de voto.

Nessa assembleia geral pode haver pequenas alterações nos resultados eleitorais, porque ao serem verificadas as actas poderá haver pequenas correcções  nas votações das diversas listas: votos nulos, considerados mal anulados. Contudo, não foi o que se passou na altura, mas se eu tivesse menos um (1) voto poderia não ser eleito.

Em Portugal, o sistema de representação proporcional permite a eleição dos vereadores, deputados e outros eleitos de acordo com esse sistema, considerando o número de votos que cada candidato ou lista obteve, proporcionalmente, tal como o nome indica. Há outros sistemas, como o sistema maioritário ou sistemas híbridos, que envolvem o proporcional e o maioritário. Contudo, o sistema proporcional parece ser o mais justo, pois permite, apesar de algumas imperfeições, que os partidos minoritários tenham representação, o que não acontece com o sistema maioritário, por exemplo.

Para determinar o número de eleitos de cada lista utiliza-se o método d`Hondt, jurista belga do século XIX, que era adepto da representação proporcional e que permite a atribuição dos mandatos pelas listas, proporcionalmente ao número de votos.

Em relação ao caso de que falo havia quatro listas de candidatos, designadas a seguir pelas letras A, B, C e D. As votações indicadas não correspondem à realidade, são meras aproximações, excepto a votação da lista C, que corresponde à votação da lista de que eu fazia parte.

As votações foram as seguintes:

                                                 Lista A - 15 682

                                                 Lista B - 6 490

                                                 Lista C - 3 137 

                                                 Lista D -    341 

O número de veradores a eleger, incluindo o presidente, era sete (7).

Como proceder para fazer a atribuição dos mandatos?

Vamos construir uma tabela com duas colunas. Na 1ª colocamos as listas e na 2ª os votos:

Listas Votos
A 15 682*
B 6 490
C 3 137
D 341

 

Como se trata de uma eleição para a câmara, a lista A elege o presidente. A seguir, o número de votos da lista A divide-se por 2 e cria-se mais uma coluna:

Listas Votos Votos/2
A 15 682* 7 841*
B 6 490  
C 3 137  
D 341  

 

Como o quociente obtido é maior que a votação da lista B, a lista A elege o 2º vereador. A seguir, o número de votos da lista A divide-se por 3 e cria-se mais uma coluna:

 

Listas Votos Votos/2 Votos/3
A 15 682* 7 841* 5 227*
B 6 490* 3 245  
C 3 137    
D 341    

 

Como o quociente obtido é menor que a votação da lista B, a lista B elege o 3º vereador. A seguir o número de votos da lista B divide-se por 2.

O quociente mais elevado elege o 4º vereador para a lista A.  A seguir, o número de votos da lista A divide-se por 4 e cria-se mais uma coluna:

 

Listas Votos Votos/2 Votos/3 Votos/4
A 15 682* 7 841* 5 227* 3 921*
B 6 490* 3 245    
C 3 137      
D 341      

 

O quociente mais elevado elege o 5º vereador para a lista A. A seguir, o número de votos da lista A divide-se por 5 e cria-se mais uma coluna:

 

Listas Votos Votos/2 Votos/3 Votos/4  Votos/5     Eleitos
A 15 682* 7 841* 5 227* 3 921* 3 136 4
B 6 490* 3 245*       2
C 3 137*         1
D 341          

 

O quociente mais elevado elege o 6º vereador para a lista B. E, por fim, o 7º vereador a ser eleito fui eu com 3 137 votos (Lista C). Se repararem o 5º quociente da lista A é 3 136 que é o arredondamento, por defeito, do quociente 3 136,4 (5º quociente da lista A). Se a votação da minha lista fosse 3 136 (menos 1 voto), eu não era eleito, porque o quociente de 15 862/5, aproximado às décimas, é maior que 3 136.

Concluindo: Por um voto se ganha, por um voto se perde.

 

Agora vou deixar para o leitor um pequeno desafio:

 

Este ano de 2009 vai haver eleições para as autarquias. Imagine que numa cidade se elegem 9 vereadores, porque a cidade tem mais de 50 mil eleitores e que a distribuição da votação foi a seguinte (5 listas):

                                         lista A  - 21 733

                                         lista B - 13 906

                                         lista C - 7 803

                                         lista D - 4 652

                                         lista F - 783

Utilizando o método de Hondt faça a distribuição dos lugares pelas cinco listas concorrentes.

Ficamos à espera das vossas respostas.

publicado por Frantuco às 19:17
link do post | comentar | favorito
Sexta-feira, 20 de Fevereiro de 2009

O jogo do NIM - segunda versão

Tal como dissemos no artigo anterior, o jogo do NIM tem algumas versões. Esta segunda versão que vamos tratar é uma das mais conhecidas e é a que é referida no filme "L`année dernière à Marienbad".

 

 

Na primeira versão apresentámos o jogo com uma só linha.

Na segunda versão pode haver duas linhas ou dezenas delas.

As regras consistem em tirar tantos objectos quantos se quiser, mas de uma só linha e ganha o jogador que tirar o último objecto.

 

A versão mais simples poderá ser o jogo com duas linhas e apenas um objecto em cada uma:

 

 

Neste caso perde o jogador que começa o jogo. É fácil de ver porquê: o jogador A, que começa só pode tirar um objecto de uma linha. Logo, a seguir, o segundo jogador tira o segundo e último objecto  e ganha.

Vamos imaginar uma versão mais complicada: duas linhas com dois e sete objectos, respectivamente:

 

¶    ¶  

¶    ¶     ¶     ¶     ¶     ¶     ¶ 

 

Neste caso, só temos a certeza de ganhar se formos nós a começar o jogo. Como?

- 1ª jogada - tiramos cinco (5) objectos da segunda linha e fica assim:

 

¶    ¶

¶    ¶

 

- 2ª jogada - o nosso adversário tem duas hipóteses: ou tira 1 (um) objecto de uma linha e nós tiramos também 1 (um) objecto da outra linha e fica assim:


 

- A jogada a seguir corresponde à versão mais simples: o nosso adversário tira um objecto e nós tiramos o outro e ganhamos.

 

 - 2ª jogada- o nosso adversário tira 2 (dois) objectos de uma linha e nós tiramos os outros dois da outra linha e ganhamos.

 

Vamos imaginar que nos propunham um jogo com três (3) linhas, organizadas do seguinte modo:

 

¶     ¶     ¶

¶     ¶     ¶     ¶    ¶

¶     ¶     ¶     ¶    ¶     ¶     ¶

 

 

 Considerando que       101 = 10

                                     102 = 100

                                     103 = 1000

                           .......................................

então

75 048 = 7 x 104 + 5 x 103+ 0 x 102+  4 x 101+ 8

 

Tal como escrevemos um número na base 10 podemos utilizar outras bases para escrever um número.

Consideremos a seguinte tabela:

 

Números base 2 base 5 base 8 base 10 base 12
7 111 12 7 7 7
14 1110 24 16 14 12
21 10101 41 25 21 19
36 100100 121 44 36 30
49 110001 144 61 49 41

 

Como se verifica escrevemos 5 números na base 10 em outras bases. Se observarmos bem verificamos que existe uma base que se destaca das outras todas pela sua simplicidade. É a base 2 que precisa apenas de dois (2) símbolos para escrever qualquer número.

Como passar um número da base 10 para qualquer base? Vamos fazer um exemplo para a base 2. Fazem-se divisões sucessivas por 2. Vamos passar o número 43, para a base 2:

  

O número 43 escreve-se na base 2 começando no último quociente como 101011, que também se pode escrever, tal como fizemos para o 75 048 na base 10:

 

101 011 = 1 x 25 + 0 x 24 + 1 x 23 + 0 x 22+ 1 x 21 + 1

 

Se fizermos os cálculos verificamos que o número 43 na base 10 se pode escrever do seguinte modo:

 

43 = 32 + 8 + 2 + 1 ou seja  25 = 32   //   23 = 8   //   21 = 2    //    20 = 1

Esta igualdade tem a ver com o teorema que afirma que "Um número inteiro é uma potência de dois (2) ou a soma de duas ou mais potências de dois (2)". A tabela que segue mostra isso mesmo:

 

 

Números              Potências de 2  Números na base 2
64 32 16 8 4 2 1
2           1 0               1  0
6         1 1 0               1  1  0
18     1    0 0 1 0               1   0  0  1  0
19     1 0 0 1 1               1  0  0  1  1
26     1 1 0 1 0               1  1  0  1  0
44   1 0 1 1 0 0               1  0  1  1  0  0

 

Para escrever qualquer número inteiro na base dois (2) basta descobrir quais as potências de 2 que somadas dão o número escolhido. Vejamos o 44.

 

            44 = 32 + 8 + 4, mas não tem o 16, nem o 2, nem o 1. Por isso, colocando por ordem as potências de 2, na posição do 32, do 8 e do 4 aparece 1 e na posição do 16, do 2 e do 1 aparece 0.

Assim 44 na base 2 escreve-se 1 0 1 1 0 0.

 

O sistema binário ou de base 2 tem variadissimas aplicações especialmente em computação. A sua utilização no jogo do NIM permite-nos encontrar uma estratégia ganhadora, utilizando a lógica do sistema binário. Vamos voltar à proposta das três linhas de objectos. Se ainda se lembram tínhamos três linhas com 3, 5 e 7 objectos. Qual a estratégia ganhadora?

Vamos construir uma tabela com estes números:

 

Números Base 2
quatro - 4 dois - 2 um - 1
3 0 1 1
5 1 0 1
7 1 1 1
  0 0 1

 

Para que serve esta tabela?

Temos os números de objectos escritos na base 2. Temos as colunas somadas, cujos resultados são da esquerda para a direita 0, 0, 1. O que significam estes valores? Se a soma é par colocamos 0, se for impar colocamos 1.

No jogo do NIM a estratégia ganhadora implica que todas as "somas" sejam 0 (pares). O que temos não é uma situação ganhadora.

O que devemos fazer se formos nós a jogar?

Temos duas jogadas possíveis. Tirar um objecto da 1ª linha, onde ficariam dois objectos. A situação ficaria:

Números Base 2
quatro - 4 dois - 2 um - 1
2 0 1 0
5 1 0 1
7 1 1 1
  0 0 0

 

Poderíamos ter feito outra jogada. Qual? Deixo ao leitor a sua descoberta.

Vamos fazer as jogadas possíveis utilizando os objectos:

                                                    

¶    ¶    ¶

¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶    ¶    ¶

 

- A primeira jogada é tirar um objecto da primeira linha para obtermos uma posição ganhadora. A situação fica assim:

 

¶    ¶

¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶    ¶    ¶

 

- Agora é o nosso adversário a jogar. Imaginemos que ele tira 3 objectos da 3ª fila.

Que jogada devemos fazer?

Podemos tirar, por exemplo, os dois objectos da 1ª linha e a posição fica assim:

 

¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶ 

 

-.Agora é novamente o nosso adversário a jogar. Se estivesse no lugar dele que jogada faria? Vamos imaginar que tira três objectos da 1ª fila. O que fazemos nós? Para continuarmos a manter a posição vencedora temos de tirar dois objectos na 2ª fila e a posição fica como segue:

 

¶    ¶

¶    ¶

 

- Agora é novamente o nosso adversário a jogar. E já perdeu. Se tirar dois objectos de uma das filas, nós tiramos os outros dois da outra fila e ganhamos.

Se tirar um objecto de uma fila, nós tiramos um objecto da outra e fica um objecto em cada fila. Como a seguir joga ele e tem de tirar um objecto de uma fila, nós tiramos o outro e ganhamos.

 

Para terminar, vamos deixar um desafio aos leitores. Não se devem esquecer de organizar uma tabela para encontrar a estratégia ganhadora.

- Somos nós a jogar e temos esta posição, que queremos transformar em posição ganhadora. Que jogada fazer? E como desenvolver o jogo perante o nosso adversário?

 

¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶

 

E se a situação fosse a seguinte, um pouco mais complicada?

 

¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶   ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶   ¶    ¶    ¶    ¶  ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶

 

Fico à espera das vossas soluções.

 

publicado por Frantuco às 11:35
link do post | comentar | favorito
Quarta-feira, 11 de Fevereiro de 2009

O jogo do NIM - primeira versão

A revisão de um filme da década de 60 do século passado, do realizador francês Alain Resnais (o filme é "L`année dernière à Marienbad"), despertou-me para a importância dos jogos nas sociedades humanas. Um dos diálogos entre duas das personagens do filme referido (vou citar de memória) dizia o seguinte:

 

- Conheço um jogo em que eu ganho sempre.

- Se você ganha sempre não é um jogo.

- É um jogo mas eu ganho sempre.

 

Que jogo era este? É um jogo bastante antigo, possivelmente de origem chinesa. Para o jogar são precisos apenas dois jogadores. É bastante simples e tem variadas versões e poucas regras. Pode ser jogado com números, traços, fósforos, moedas, botões, sementes,... uma infinidade de objectos.

 

Vamos apresentar duas versões.

 

A primeira versão consta apenas de um conjunto com um número variado de objectos alinhados.

Regras: Ganha quem tirar o último objecto; cada jogador pode tirar até três objectos em cada jogada.

 

Vamos começar por considerar 20 objectos:

 

¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶    

1     2     3     4     5     6     7     8     9    10   11   12  13     

 ¶    ¶     ¶     ¶     ¶     ¶     ¶

14  15    16   17   18  19   20

 

Como ganha quem tirar o último objecto, vamos tentar descobrir como ganhar se for o nosso adversário a iniciar o jogo (jogador A). Que objectos devemos tirar para ganhar?

 

- 1ª jogada: o nosso adversário (jogador A) tira, por exemplo 3 objectos e nós 1. A situação fica do seguinte modo:

 

¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶    

5     6     7     8     9    10   11   12  13     
¶     ¶      ¶     ¶     ¶     ¶     ¶

14  15    16   17   18   19    20

 

- Na segunda jogada, o jogador A tira 2 objectos e nós também 2. A situação fica assim:

 

¶     ¶     ¶     ¶     ¶    ¶     ¶      ¶     ¶     ¶     ¶     ¶

9    10   11   12  13    14  15    16   17   18   19    20

 

- 3ª jogada: o jogador A tira 1 objecto, por exemplo, e nós tiramos 3. A situação fica como segue:

 

     

¶       ¶     ¶      ¶     ¶     ¶     ¶     ¶

13    14   15    16   17   18   19    20

 

- Na jogada seguinte, o nosso adversário tira, por exemplo, 3 objectos e nós 1. Neste momento já perdeu. A situação fica assim:

 

¶      ¶     ¶     ¶

17   18   19    20

 

- Na última jogada, cumprindo sempre as regras do jogo, sela qual for o número de objectos retirados pelo nosso jogador A, nós tiramos sempre o último e ganhamos.

 

Impõe-se uma pergunta: Qual é a estratégia ganhadora?

 

- Basta analisar as jogadas. Nós tiramos sempre os objectos que completam os múltiplos de 4: 4 - 8 - 12 - 16 - 20. Porquê? deixamos a interrogação.

 

Se formos nós a iniciar o jogo, como ganhar? É possível ganhar sempre?

 

Façamos uma experiência com 20 objectos. Vamos simular um conjunto de jogadas:

 

1ª jogada - Vamos tirar 3 objectos, por exemplo. Se o nosso adversário tirar igualmente 3 objectos, a situação o jogo fica com últimos 14.

Na 2ª jogada nós tiramos 2 objectos e a partir deste momento temos uma situação ganhadora.

Vamos tirar nas jogadas seguintes os objectos necessários para completar os múltiplos de 4, tal como no caso anterior.

 

As estratégias ganhadoras dependem do número de objectos com que estamos a jogar. Vamos utilizar, por exemplo, 37 objectos:

 

&      &     &     &      &     &     &     &     &     &     & 

1       2     3     4       5     6      7     8     9     10   11


&      &     &     &      &     &     &     &     &     &     &                   

12   13    14   15    16    17    18   19    20   21   22      


&      &     &     &      &     &     &     &     &     &     &      

23    24   25   26     27   28    29   30    31   32    33


&      &     &     &      

34    35   36    37

 

Vamos simular o jogo, mantendo sempre as regras iniciais e com o nosso adversário a iniciar o jogo.

- Para iniciar o jogador A (nosso adversário) tira, por exemplo 2 objectos. Quantos objectos devemos tirar nós para construir ou iniciar uma estratégia ganhadora?

Se analisarmos a situação concluiremos que a nossa jogada deve ser tirar 3 objectos; portanto até ao 5º objecto.

A partir daqui as nossas jogadas devem orientar-se no sentido de tirarmos os objectos números 5 - 9 - 13 - 17 - 21 - 25 - 29 - 33 - 37, ou seja múltiplo de 4 mais 1.

Porquê? Mais uma vez deixamos a interrogação para os leitores.

E se formos nós a iniciar o jogo? Qual a estratégia ganhadora?

Mais uma vez vamos fazer uma simulação:

- Se tirarmos, por exemplo, três objectos (3) e o nosso adversário tirar também 3, que jogada devemos fazer a seguir para construir uma estratégia ganhadora?

É evidente que a nossa 2ª jogada deve ser 3 e ficamos na posição de controlar o evoluir do jogo, tal como na situação anterior.

Já dissemos que o número de objectos condiciona a estratégia.

Um pequeno desafio para os leitores:

 

- Que números devemos tirar para construir uma estratégia ganhadora, se o nosso adversário for o primeiro a tirar objectos e estivermos a jogar com 43 objectos? E se começarmos nós o jogo?

 

Nota: A 2ª versão será publicada no próximo artigo.

 

 

publicado por Frantuco às 23:15
link do post | comentar | favorito
Quarta-feira, 4 de Fevereiro de 2009

A travessia da ponte - novo problema

A nossa família Crespo, a família das caminhadas e aventuras, tomou o gosto à travessia da ponte e decidiu descobrir outros caminhos alternativos para o percurso que tinham efectuado da primeira vez. Como devem estar lembrados, seguiram o rio Erges até à confluência com o Tejo. Desta vez afastaram-se do rio, utilizando uma carta, mas sempre com a intenção de passarem pela ponte para fazerem de novo a travessia.


Entretanto já tinham ganho alguma experiência de caminhadas e a sua marcha era mais segura, mais rápida e como já tinham aprendido a orientar-se através de uma carta demoravam muito menos tempo para fazer os mesmos percursos.


Tal como tinham planeado chegaram à ponte em pleno dia, mas já sabiam que apenas dois caminhantes podiam atravessá-la de cada vez.

 

 

Como já eram mais rápidos calcularam o tempo que cada um levaria agora a atravessar a ponte e concluiram o seguinte:

- o Ângelo que sempre se empenhou em caminhar bem e depressa consegue agora atravessar a pote em 1 minuto;

 

- a irmã Laura também melhorou substancialmente o seu tempo e gasta agora 3 minutos;

 

- o pai Geraldo descobriu que gasta pouco mais de metade do tempo que gastou na primeira vez - 6 minutos;


- por sua vez o avô Marcelo é um exemplo perfeito de como o exercício físico é óptimo para a saúde e gasta agora apenas 9 minutos.


Mas a família Crespo, desta vez, alargou e vão mais dois elementos na caminhada - a mãe Leonor e o primo do Ângelo e da Laura, o Leandro que veio passar o fim de semana com eles e a quem já tínhamos feito referência no primeiro problema.


O pai Geraldo, "democraticamente", decidiu que a mulher Leonor atravessará a ponte em 8 minutos e o Leandro em 4 minutos. Ele baseou-se na forma como eles se tinham portado na caminhada, até ao momento.


O pai Geraldo e o avô Marcelo organizaram um plano de modo a fazerem a travessia da ponte no mínimo de tempo possível e chegaram à conclusão que era possível fazer a travessia dos 6 (seis) elementos em 31 minutos.


Talvez queira o leitor tentar descobrir como é que o pai Geraldo e o avô Marcelo organizaram a travessia de modo a demorarem apenas 31 minutos.

palavras-chave:
publicado por Frantuco às 23:41
link do post | comentar | favorito

.mais sobre mim

.pesquisar

 

.Janeiro 2010

Dom
Seg
Ter
Qua
Qui
Sex
Sab
1
2
3
4
5
6
7
8
9
10
12
13
14
15
17
18
19
20
21
22
23
25
26
27
28
29
30
31

.posts recentes

. O Ano 2010 e as potências...

. O Ano de 2010 e as potênc...

. O Ano de 2010 e as potênc...

. As cidades, as vilas, as ...

. O caderno de exercícios "...

. Os contos das noites de i...

. Mais uma vez o regresso à...

. Grandes Matemáticos - Pit...

. Cereais, legumes, medidas...

. Memórias I

. O Labirinto

. Sapos e rãs ou ovelhas e ...

. Rãs e Sapos ou Ovelhas e ...

. HIPÁTIA DE ALEXANDRIA

. A decomposição de números...

. Grandes Matemáticos - Leo...

. Os algoritmos - o número ...

. Os algoritmos - o código ...

. Os caminhos do João

. As probabilidades no dia ...

. As probabilidades no dia ...

. O tempo, os relógios e as...

. As probabilidades e os an...

. Vamos aos gambuzinos

. O jardim de pedra

. De novo as eleições - as ...

. Os frutos secos do Natal

. As caminhadas, as pesagen...

. O Método de Hondt

. O jogo do NIM - segunda v...

. O jogo do NIM - primeira ...

. A travessia da ponte - no...

. Algoritmos - A fórmula de...

. Algoritmos - O teorema de...

. Um problema de idades

. INVERSÕES

. A travessia da ponte

. O carteiro, as idades e o...

. A herança do lavrador

. O relógio, as horas e os ...

. A decomposição de números...

. O problema das idades

. CAPICUAS

. DINHEIRO FALSO

. O Pombal das cem pombas

. Números e cálculo mental

. Poesia Matemática

. Os algoritmos - raiz quad...

. Os algoritmos - raíz quad...

. Os algoritmos - algoritmo...

.arquivos

. Janeiro 2010

. Dezembro 2009

. Novembro 2009

. Outubro 2009

. Agosto 2009

. Julho 2009

. Junho 2009

. Maio 2009

. Abril 2009

. Março 2009

. Fevereiro 2009

. Janeiro 2009

. Dezembro 2008

. Novembro 2008

. Outubro 2008

. Setembro 2008

. Agosto 2008

. Julho 2008

.palavras-chave

. todas as tags

.links

blogs SAPO