Newsgroup: it.hobby.enigmi
Titolo: Il foglio di francobolli

Sempre dalla Bocconi:
E' possibile ottenere tutti i numeri interi da 1 a 36 staccando uno o
piu' francobolli da un foglio rettangolare di due francobolli per tre,
portanti i valori 1,2,3,5,8,17 e sommando questi valori.
I valori restanti devono pero' formare sempre un "pezzo" solo (devono
cioe' rimanere attaccati almeno per un lato).
Potete ricostruire questo foglio di francobolli ?
L'esempio della figura non va bene in quanto e' impossibile ottenere le
somme 7,10,12,15,24,27 e 32.
|¯¯¯¯|¯¯¯¯|¯¯¯¯|
|  1 |  2 |  3 |
|____|____|____|
|    |    |    | 
|  5 |  8 | 17 |
|____|____|____|
:) dario

...

mi pare che non sia possibile; ecco il ragionamento:
Stacco 32, rimane 4 che puo' essere formato solo come 3+1
Quindi i numeri 3 ed 1 devono essere adiacenti (formano una
tessera di domino)
Stacco 29, rimane 7 che puo' essere formato solo come 5+2
Anche 5 e 2 formano una tessera di domino
Stacco 24, rimane 12, che puo' essere solo 8+3+1
la casella 8 deve essere adiacente alla tessera 3+1
Stacco 21, rimane 15, che puo' essere solo 8+5+2
la casella 8 deve essere adiacente alla tessera 5+2
Stacco 15, rimane 21, che puo' essere solo 17+3+1
17 deve essere adiacente alla tessera 3+1
Stacco 12, rimane 24, che puo' essere solo 17+5+2
17 deve essere adiacente alla tessera 5+2
Stacco 30, rimane 6, che puo' essere 5+1 oppure 3+2+1
in ogni caso la tessera 5+2 deve essere adiacente alla
tessera 3+1
Quindi le due tessere 3+1 e 5+2 devono essere adiacenti tra
loro, ed entrambe adiacenti sia ad 8 che a 17
indicando con xx xx ed yy yy le due tessere, la disposizione
deve essere del tipo:
xx xx 17
08 yy yy
questa disposizione pero' non consente di ottenere 6,
infatti dovrei staccare due xx ed una yy (o viceversa) ed in
ogni caso spezzerei il foglio
ciao
paolo


1    3    17
8    2    5
Alcune considerazioni per circoscrivere il problema:
1) Far restare i numeri 1,2,3,5,8,17,19,28,31,33,34,35,36 non crea alcun
problema perche' questi "resti" si ottengono o lasciando un solo francobollo
o lasciandone 5 (o 6 nel caso di 36). In ogni caso quando lascio 1,5,6
francobolli questi devono essere giocoforza uniti lungo un lato (il problema
nemmeno si pone se lascio un solo francobollo).
2) I restanti numeri cioe'
4,6,7,9,10,11,12,13,14,15,16,18,20,21,22,23,24,25,26,27,29,32 possono essere
divisi a loro volta in due gruppi:
PRIMO GRUPPO: quelli per cui la rimozione deve essere fatta per forza in un
dato modo: esempio: il quattro si puň ottenere prelevando SOLAMENTE il 3 e
l'1.
SECONDO GRUPPO: quelli per cui la rimozione puň essere fatta scegliendo tra
due opzioni: esempio il sei lo posso ottenere prelevando 5 e 1 OPPURE 3,2,1.
Conviene focalizzare l'attenzione sul primo gruppo costituito dai casi in
cui i francobolli rimasti hanno un valore di:
 32,29,24,21,15,12,7,4
Prelevo 4   (3+1)      ==> Rimane 32 (2+5+8+17)
Prelevo 7   (5+2)      ==> Rimane 29 (1+3+8+17)
Prelevo 12 (8+3+1)  ==> Rimane 24 (17+2+5)
Prelevo 15 (8+5+2)  ==> Rimane 21 (2+5+8)
Prelevo 21..... (simmetrico rispetto a 18)==> Rimane 15...
Quindi ciň che so e' che alla fine dopo aver prelevato francobolli per un
valore di 32,29,24.... mi rimangono i seguenti "frammenti": 3,1 - 5,2 -
8,3,1 - 8,5,2 - 2,5,8,17 - 1,3,8,17 - 17,2,5 - 2,5,8.
E' evidente quindi che ad esempio ,1e3, dovranno essere sul foglio uniti
lungo un lato cosě come 2e5.
Inoltre se considero il foglio come come costituito da 3 colonne A;B;C e 2
righe 1;2 č anche evidente che 1e3 e 2e5 non potranno occupare
contemporaneamente le caselle centrali B1 eB2 altrimenti quando prelevo 4 e
7 lascio due distinti frammenti.
So inoltre che a 1 e 3 (che sono uniti lungo un lato) deve essere
legatoanche un 8 (quando prelevo 24 mi rimane 1,3,8) qiundi  ho due
possibilitŕ 1,3,8 e 8,3,1 (ovviamente non solo in una striscia 3x1 ma anche
in una sorta di L).
Proseguendo cosě, ripetendo il discorso per 2 e5 .... alla fine si ottengono
18 distinte disposizioni che soddisfano i prelevi di francobolli che possono
avvenire in un solo modo.
Confrontando queste 18 disposizioni con i prelievi che possono essere
effettuati in piů di un modo (es 6=5+1=3+2+1...) vediamo che solo una (o
almeno io ne ho trovata una sola :-) soddisfa le condizioni imposte cioč:
A1=1   B1=3   C1=17    A2=8    B2=2    C2=5
  1      3       17
   8     2        5
(oltre a ovviamente rotazioni e rifflessioni)
Ciao Paolo (veramente bello questo rompicapo)

 8    2    5
Non vedo come tu possa prelevare 6, lasciando uniti gli altri
francobolli.
Ho trovato anch'io le stesse difficoltà che a trovato l'altro Paolo
(Licheri)
Ciao
Gianni

 francobolli.
Stai scherzando, vero?
Ti rimane una s di Tetris :-)
MaxArt

 Ciao Paolo (veramente bello questo rompicapo)
No, veramente brutto questo rompicapo.
Più che altro, è perché venivano assegnati ben 14 punti ad un problema che
richiedeva ad un certo punto la forza bruta del controllo dei singoli casi.
Questa per me è una *pessima* caratteristica.
Naturalmente, me la prendo così tanto soprattutto perché l'ho sbagliato :-(
Controllando i singoli casi, mi dev'essere sfuggito quello giusto...
disperato (dovevo consegnare!), con un mal di testa da paura (la
concentrazione stava svanendo, e le meningi cominciavano a farsi sentire),
ci ho messo uno di quelli più probabili e m'è andata male. É stata una così
sottile differenza...
Cmq io ho ragionato così, notando subito che 32 si poteva scrivere solo
come:
32 = 17 + 8 + 5 + 2
Gli unici modi per staccare 4 pezzi sono questi:
* - *      - * *      - - *
* - *      - * *      * * *
(gli asterischi sono i pezzi staccati)
Tuttavia il primo modo è da escludere perché l'1 deve stare in alto a sx.
Restano due configurazioni, che chiamo rispettivamente C1 e C2.
C1:
1 a b
3 c d
C2:
1 3 d
a b c
A questo punto, ho solo da controllare 4! + 4! = 48 combinazioni, ed
eleminare più casi possibili.
Partiamo col 7, ottenibile solo con 2+5. In C1, quindi, 2 e 5 non possono
occupare assieme i posti a e c, b e c, a e d; in C2, invece, i posti b e d:
altri 8 casi eliminati.
Oppure il 18 (ottenibile come 17+1 oppure con la somma dei restanti): ne
segue che in C1 il 17 non può stare in c e in C2 non può stare in b. Si
eliminano altri tot casi.
Poi si considera il 12, e allora in C2 l'8 non può stare in c e così via con
altre considerazioni.
Per quanto mi sforzassi, però non potevo ottenere la soluzione con le sole
considerazioni, ergo forza bruta.
:-(
MaxArt


5+1 ovviamente e lascio un frammento che contiene 2,3,8e17

 MaxArt
Scusa, hai ragione
Ciao
Gianni