Problema di Giuseppe Flavio

[Mario Coppo]

Enne persone si mettono in cerchio e contando fino a kappa, da una prima
persona qualsiasi, si eliminano quelle che capitano alla fine della conta.

Esiste una formula che dia la posizione che deve avere una persona perche'
risulti l'ultima ad essere eliminata dati enne e kappa ?

Esistono algoritmi che creano delle liste o vettori che vengono percorsi
in vari modi per trovare la soluzione, ma ne esiste uno che non utilizzi
liste, vettori o quantaltro ?

La funzione f(n,k,i) (enne=numero persone iniziale, kappa=numero
utilizzato per la conta e i=posizione variabile da uno a enne) genera una
permutazione di enne elementi. Dato enne e variando kappa le permutazioni
sono diverse ?

Data una permutazione di enne elementi e' possibile trovare un kappa che
la generi ?

Alcune risposte le ho travate ma senza una dimostrazione formale, qualcuno
ha suggerimenti da darmi ?

Mario

[Cosimo Laddomada]

Mario Coppo wrote:

> Enne persone si mettono in cerchio e contando fino a kappa, da una prima
> persona qualsiasi, si eliminano quelle che capitano alla fine della conta.
>
> Esiste una formula che dia la posizione che deve avere una persona perche'
> risulti l'ultima ad essere eliminata dati enne e kappa ?

Mario, la vedo nera :-(
Mi sa che una formula generale, se esiste, sara' complicatissima, non
parliamo poi come dimostrarla.

> Esistono algoritmi che creano delle liste o vettori che vengono percorsi
> in vari modi per trovare la soluzione, ma ne esiste uno che non utilizzi
> liste, vettori o quantaltro ?

"Quant'altro" in che senso? Perche', se mi togli le liste e i vettori, con
cosa vuoi operare? Rimarrebbero i set, ma nel momento in cui stabilisci un
ordine in un set...

Comunque, una funzione Pascal te la posto di seguito; eventualmente, mettila
insieme agli altri algoritmi.

function f(Sup, Delta, inizio: Integer): Integer;
var Ar: array[1..100] of Integer;
i, eliminati: Byte;

procedure Next;
begin
if inizio=Sup then inizio := 1 else Inc(inizio);
if Ar[inizio] = 0 then Next
end;

begin
for i:=1 to Sup do Ar[i] := i;
eliminati := 0;
repeat
for i:=1 to Delta do Next;
Ar[inizio] := 0;
Inc(eliminati);
until eliminati = Sup-1;
Next;
result := inizio;
end;

> La funzione f(n,k,i) (enne=numero persone iniziale, kappa=numero
> utilizzato per la conta e i=posizione variabile da uno a enne) genera una
> permutazione di enne elementi. Dato enne e variando kappa le permutazioni
> sono diverse ?
>
> Data una permutazione di enne elementi e' possibile trovare un kappa che
> la generi ?

Queste cose che dici sulle permutazioni non le ho capito. :-)

> Alcune risposte le ho travate ma senza una dimostrazione formale, qualcuno
> ha suggerimenti da darmi ?

Sarei curioso di conoscerle le "risposte" di cui parli, se si riferiscono
alla formula di cui parli all'inizio. Almeno, per la dimostrazione avremmo
qualche indicazione concreta.

---------------------------------------------------
Mimmo Laddomada (InfoMath) c.lad...@agora.stm.it
Via Montenero, 31/33 - I-73047 MONTERONI (LE)
Fax: +39-(0)832-326532 - Tel: +39-(0)832-321560

[G. DEL ZZ FROM ADDR Resta]

In article <mario-16059...@bach.tradenet.it>, ma...@tarta.avnet.it
(Mario Coppo) wrote:

> Enne persone si mettono in cerchio e contando fino a kappa, da una prima
> persona qualsiasi, si eliminano quelle che capitano alla fine della conta.
>
> Esiste una formula che dia la posizione che deve avere una persona perche'
> risulti l'ultima ad essere eliminata dati enne e kappa ?

A questo problema e' dedicata tutta la sezione 1.3 del bellissimo libro
"Concrete Mathematics" di Graham, D.E. KNUTH e Patashnik.
(Non so se esiste una, forse inopportuna, traduzione italiana).

GKP partono dal problema di eliminare 1 ogni 2 da un cerchio iniziale di n
persone. Trovano la soluzione e poi generalizzano. La soluzione finale
non e' complicatissima ma si basa su un po' di cose che non trovano
spazio in questi margini.... Ti posso dire che si puo' costruire una
ricorrenza in cui entrano le rappresentazioni in base k.

Ciao.
Giovanni Resta

[Maurizio Codogno]

In article <resta-18059...@mac-resta.imc.pi.cnr.it>,
G. "DEL ZZ FROM ADDR" Resta <re...@ZZimc.pi.cnr.it> wrote:

% A questo problema e' dedicata tutta la sezione 1.3 del bellissimo libro
% "Concrete Mathematics" di Graham, D.E. KNUTH e Patashnik.
% (Non so se esiste una, forse inopportuna, traduzione italiana).

Secondo la pagina di DEK, si`:

Italian translation edited by Giovanni Monegato, Matematica Discreta
(Milan: Editore Ulrico Hoepli, 1992), xviii+607pp.

.mau.

(la pagina e` http://www-cs-faculty.stanford.edu/~knuth/gkp.html)

[Dario Uri]

Mario Coppo wrote:

> Enne persone si mettono in cerchio e contando fino a kappa, da una
> prima
> persona qualsiasi, si eliminano quelle che capitano alla fine della
> conta.
>
> Esiste una formula che dia la posizione che deve avere una persona
> perche'
> risulti l'ultima ad essere eliminata dati enne e kappa ?
>

Puoi trovare un metodo ricorrente dato da P.G.Tait nel 1900 in
"Mathematical Recreations & Essays" Rouse Ball & M.Coxeter pagg.32/36.
Arrivata alla 11esima edizione.
dario