ATRACTOR
No âmbito de uma colaboração
entre a Gazeta e o Atractor, este
é um espaço da responsabilidade
do Atractor, relacionado com
conteúdos interactivos do seu
site www.atractor.pt .
Quaisquer reacções ou sugestões
serão bem-vindas para
[email protected]
JOGOS ISOMORFOS
1HVWHDUWLJRSURSRPRVDROHLWRUXPDYHUVmROXPLQRVDGRMRJRGDV
WRUUHVGH+DQyL
PDJLQHPRVXPMRJRIRUPDGRSRUXPDÀODGHOkPSDGDVHP
'
TXH FDGD OkPSDGD SRGH HVWDU QXP GH GRLV HVWDGRV DFHVD
RXDSDJDGD
Figura 2
'HVLJQH 897: SDUD FDGD 7 XPD VXFHVVmR GH FOLTXHV GH FRP"
SULPHQWRPtQLPRTXHDSOLFDGDDXPDÀODGH7OkPSDGDVGDV
Figura 1
&OLFDQGRQXPDGHODVRXVyHVVDPXGDGHHVWDGRRXÀFDP
TXDLVDVSULPHLUDVQй( HVWmRDSDJDGDVVyPXGDRHVWDGRGD
WRGDVQRHVWDGRHPTXHHVWDYDP4XDOGDVGXDVRFRUUrQFLDV"
OkPSDGD7(GHVLJQH-97:RQ~PHURGHFOLTXHVGH897:3DUWLQ"
WHP OXJDU GHSHQGHUi VHJXQGR XPD UHJUD SUHFLVD GR HVWDGR
GRGHXPDÀODGH7OkPSDGDVDSDJDGDVVyVHFRQVHJXLUiDFHQ"
GDVOkPSDGDVGDÀOD$FRQVHOKDPRVROHLWRUDTXHWHQWHGHVFR"
GHUDOkPSDGD7TXDQGRHQWUHDVDQWHULRUHVDSHQDVHVWHMDDFH"
EULUHVVDUHJUDSRUVLPHVPRH[SHULPHQWDQGRFRPXPPRGH"
*)%)%&#%+,&#$%Qй( HFRQVHJXHVHFKHJDUDHVVHHVWDGRXVDQGR
ORYLUWXDOGRMRJRGLVSRQtYHOHP>@3DUDXVDUHVVHPRGHORR
SUHFLVDPHQWHRVFOLTXHVGH)Qй²йHPQ~PHURGHIQй²й&OL"
4"&.,)"
4"&.,)"GHYHUiWHUR
+56%$70DWKHPDWLFD3OD\HUTXHSRGHUiVHU
FDQGRGHSRLVQDOkPSDGD7ÀFDUmRDSHQDVDFHVDVDVOkPSDGDV
LPSRUWDGR GH >@ 6H R OHLWRU QmR GHVHMDU ID]HU HVVH H[HUFtFLR
Qй!й% #% 7 H FRP )Qй²й DSDJDUVHi D OkPSDGD Qй²й 3RUWDQWR
GHYHOHUDJRUDQRÀQDO GRWH[WRRHQXQFLDGRGDUHJUD&RQKH"
1
;'
#''
FLGD HVVD UHJUD FRQVLGHUHVH R VHJXLQWH SUREOHPD SDUD XPD
1RWDQGR TXH ) ^`
ÀODFRP7OkPSDGDVWRGDVDSDJDGDVVHUiSRVVtYHOXWLOL]DQGR
XP
XPFOLTXHQDOkPSDGD
FOLTXHVDGHTXDGRVFRQVHJXLUTXHDSHQDVD~OWLPDOkPSDGDÀ"
DFHQ
DFHQGHDH
Iйй йWHPRV
TXHDFHVD"6HIRUTXDORQ~PHURPtQLPRGHFOLTXHVDXVDU"(
)йQ
Q % #% IйQ GHÀQLGRV SRU
KDYHUiDSHQDVXPDRXPDLVGRTXHXPDVXFHVVmRGHFOLTXHV
UHFR
UHFRUUrQFLDHDXQLFLGDGH
FRPRQ~PHURPtQLPRTXHFXPSUDHVVHREMHWLYR"2OHLWRUSR"
&#% 8
8 ÀFD WDPEpP HVWDEH"
GHUiXWLOL]DURMRJRYLUWXDOSDUDYiULRVYDORUHVGH7SURFXUDQGR
OHFL
OHFLGD(FRPRDIXQomR
%
2
GHÀQLGD SRU JQ Qй²й
GHÀQ
JDVWDURQ~PHURPtQLPRGHFOLTXHV
'HFRUUH GD UHJUD JHUDO TXH VH DV SULPHLUDV Qй( OkPSDGDV
VDWLVID] WDPEpP D Jй VDWL
HVWLYHUHPDSDJDGDVRVPHVPRVFOLTXHVTXHDFHQGHPDOkPSD"
#% )% JйQ йJQй²ййй VHUi
&)%7VHHVWDYDDSDJDGDWDPEpPDDSDJDPVHHVWDYDDFHVD
I J
J
Figura 3
ATRACTOR
Jogos isomorfos
03
$R MRJDU HVWH MRJR RFRUUH LPHGLDWDPHQWH SHQVDU QXP RX"
WURFXMDHVWUXWXUDGHUHVROXomRpPXLWRVHPHOKDQWH²RSRSXODU
MRJRGDV7RUUHVGH+DQyL/HPEUHPRVUDSLGDPHQWHDVUHJUDV
QXPWDEXOHLURFRPWUrVKDVWHVHGLVFRVGHUDLRVWRGRVGLIHUHQWHV
SRGHVHGHFDGDYH]PXGDURGLVFRGHFLPDGHXPDKDVWHSDUD
RXWUD KDVWH GHVGH TXH QXQFD VH FRORTXH XP GLVFR TXDOTXHU
VREUHRXWURPDLVSHTXHQR3DUWLQGRGHXPDSLOKDGHGLVFRVGH
GLkPHWURVGHFUHVFHQWHVQXPDGDVKDVWHVHQHQKXPGLVFRQDV
RXWUDVGXDVTXHUVHWUDQVSRUWDUDTXHODSLOKDSDUDRXWUDKDV"
WHSUHYLDPHQWHÀ[DGD&RPRRID]HUQXPQ~PHURPtQLPRGH
MRJDGDV"2MRJRpWULYLDOTXDQGRDSLOKDVyWHPXPGLVFR(
VHMiRVRXEHUPRVUHVROYHUSDUDXPDSLOKDGHQй( HWLYHUPRV
-$)%&#%7SRGHUHPRVWUDQVIHULURVQй( GLVFRVGHFLPDSDUDD
Figura 4
KDVWHGLIHUHQWHGDLQLFLDOHGDÀQDOGHSRLVPXGDURGLVFRPDLRU
SDUDDÀQDOHQRYDPHQWHWUDQVSRUWDUDSLOKDGRVDQWHULRUHVQй( SDUDFLPDGRGLVFRPDLRU'HQRWDUDSHQDVTXHFRPRRVQй( GLVFRVVmRWRGRVPDLVSHTXHQRVGRTXHRPDLRUGHWRGRVRV
PRYLPHQWRV´SHUPLWLGRVµVmRRVPHVPRVTXHUXPDKDVWHHV"
WHMDYD]LDTXHUMiOiWHQKDRPDLRUYHUÀJXUDHPTXH7 D
FROXQDLQLFLDOpDGHEDL[RHDÀQDOpDGDGLUHLWD2SURFHVVRH
DFRQFOXVmRVmRDQiORJRVDRVGRMRJRDQWHULRU
&RQVWDWDGD HVWD VHPHOKDQoD HQWUH DV UHVROXo}HV GRV GRLV
SUREOHPDV p QDWXUDO SURFXUDU OHYiOD XP SRXFR PDLV ORQJH
6HUi TXH SRGHPRV HVWDEHOHFHU XPD FRUUHVSRQGrQFLD QDWXUDO
HQWUHRVGRLVMRJRVHRVUHVSHWLYRVSDVVRVGHUHVROXomR",VWRp
TXHUHUtDPRVHVWDEHOHFHUXPDFRUUHVSRQGrQFLDELXQtYRFDQDWX"
UDOHQWUHRFRQMXQWRGDVGLIHUHQWHVGLVWULEXLo}HVSRVVtYHLVGRV
7GLVFRVGDVWRUUHVGH+DQyLSHODVWUrVKDVWHVHDVGLYHUVDVGLV"
WULEXLo}HVGH´!*),!,')'!+!%!(!,µQXPDÀODGH7OkPSDGDVGH
PRGRTXH
1. 2VGLVFRVHVWLYHVVHPWRGRVQDKDVWHLQLFLDOVHHVyVHDV
OkPSDGDVHVWLYHVVHPWRGDVDSDJDGDV
22VGLVFRVHVWLYHVVHPWRGRVQDKDVWHÀQDOVHHVyVHDSHQDV
Figura 5
D~OWLPDOkPSDGDHVWLYHVVHDFHVD
3$XPPRYLPHQWRSHUPLWLGRGHXPDKDVWHSDUDRXWUDFRU"
UHVSRQGHVVHRPHVPRHIHLWRTXHWHULDXPFOLTXHQDÀODGH
OkPSDGDVTXHSURYRFDVVHPXGDQoDGHHVWDGRGHXPDOkP"
SDGDHYLFHYHUVD
TXH HP FDGD MRJDGD R Q~PHUR GH SRVVLELOLGDGHV GHPXGDU
GHFRQÀJXUDomRQmRpRPHVPRQRVGRLVMRJRV1RFDVRGDV
WRUUHVGH+DQyLTXDQGRWRGRVRVGLVFRVHVWmRQXPDPHVPD
KDVWHWUrVFDVRVSRVVtYHLVKiGXDVMRJDGDVSRVVtYHLVRGLVFR
6REHVWDIRUPDpIiFLOFRQFOXLUTXHRSUREOHPDQmRWHPVROX"
PDLVSHTXHQRSRGHLUSDUDTXDOTXHUGDVGXDVKDVWHVYD]LDV(
omRQmRH[LVWHXPDWDOFRUUHVSRQGrQFLDELXQtYRFD%DVWDQRWDU
HPWRGRVRVRXWURVFDVRVDOpPGDVGXDVMRJDGDVFRPRGLVFR
04
GAZETA DE MATEMÁTICA r169
PDLVSHTXHQRïTXHHVWiVHPSUHHPFLPDQXPDKDVWHïKiRX"
ULRU(LVVRHTXLYDOHDTXHDVMRJDGDVVHMDPDOWHUQDGDPHQWHGR
WUDGHRXWURGLVFRVHKRXYHUXPDKDVWHYD]LDpRPRYLPHQWR
GLVFRPDLVSHTXHQRHGHRXWUR4XHUGL]HUHVWHMRJRGDVWRUUHV
SDUD HOD GR GLVFR HP FLPD GD KDVWH TXH QmR FRQWpP R GLVFR
GH+DQyLGHUHJUDVPDLVH[LJHQWHVDFDEDSRUVHUPDLVIiFLOGR
PDLVSHTXHQRVHQmRKRXYHUpRPRYLPHQWRHQWUHDVKDVWHV
TXHRGHUHJUDVPDLVSHUPLVVLYDV2SDUDGR[RpDSDUHQWHDV
TXH QmR WrP R GLVFR PDLV SHTXHQR TXH HQYLD R PHQRU GRV
QRYDVUHJUDVLPSHGHPTXHRMRJDGRUVHSHUFDHPFDPLQKRV
GRLVGLVFRVSDUDFLPDGRPDLRU1RMRJRGDVOkPSDGDVKiGRLV
PDLVORQJRV(VWDPRVSRLVFRPHVWDYHUVmRQXPDVLWXDomR
FDVRVVHWRGDVDVOkPSDGDVHVWLYHUHPDSDJDGDVRXDSHQDVD
LGrQWLFDjGRMRJRGDVOkPSDGDVRTXHQRVGHL[DHVSHUDQoDGH
~OWLPDHVWLYHUDFHVDVyKiXPFOLTXHFRPHIHLWRYLVtYHOQDSUL"
FRQVHJXLUPRV HQFRQWUDU D HTXLYDOrQFLD HQWUH HVWD YHUVmR GR
PHLUDOkPSDGDHPWRGRVRVRXWURVFDVRVDOpPGRFOLTXHQD
MRJRGDVWRUUHVGH+DQyLHRGDVOkPSDGDV3DUDGHÀQLUPRV
SULPHLUDOkPSDGDKiRFOLTXHQDOkPSDGDDVHJXLUjSULPHLUD
D FRUUHVSRQGrQFLD FRPHFHPRV SRU LPDJLQDU RV 7 GLVFRV GD
TXHHVWLYHUDFHVDÀJXUD3RUWDQWRQHVWHMRJRGXDVMRJDGDV
SLOKDQXPHUDGRVSRURUGHPFUHVFHQWHGRVUHVSHWLYRVUDLRVGH
VmR SRVVtYHLV H[FHWXDQGR GXDV VLWXDo}HV HP TXH Ki DSHQDV
D 7 R FtUFXOR YLUWXDO QD EDVH GD KDVWH GH SDUWLGD FRP XP
XPDHQTXDQWRQRRXWURMRJRKiWUrVMRJDGDVSRVVtYHLVH[FH"
UDLRXPSRXFRPDLRUGRTXHRGLVFR7RPDLRUGDSLOKDVHUi
WXDQGRWUrVVLWXDo}HVHPTXHKiDSHQDVGXDV5HODWLYDPHQWH
YLVWRFRPRRGLVFRQй. 4XDQWRDRVRXWURVGRLVGLVFRVYLUWXDLV
DRMRJRGDVOkPSDGDVQRWHPRVTXHQRFDVRJHUDOGRVGRLVFOL"
GRWDEXOHLURVHUmRDLQGDPDLRUHVFKDPHPRVOKHVQй. HQй. TXHVSRVVtYHLVXPGHOHVpRPHVPRTXHRDQWHULRUHSRUWDQWR
&RPHVWDFRQYHQomRSRGHUtDPRVWHQWDUGHÀQLUDFRUUHVSRQ"
UHS}HRHVWDGRDQWHULRU2UDQXPDSURFXUDGHFRPRUHVROYHU
GrQFLDTXHSURFXUDPRVSHODVHJXLQWHUHJUDPXLWRVLPSOHV!'
R MRJR QR PHQRU Q~PHUR GH FOLTXHV SRVVtYHO D UHSHWLomR GR
5<2+!(!'/'),#3'!+!%!(!',)')',=',)'&'($,*&'
/
/
/'),#$>)"'+&6,!(&'($")#!
?
FOLTXH DQWHULRU QXQFD GHYH VHU IHLWD 0DV H[FOXLQGR HVVD UH"
2)7#)',&4")'&'($,*&'Nйй;
SHWLomRRVFOLTXHVÀFDPGHWHUPLQDGRVGHPDQHLUD~QLFDLVWR
9HULÀTXHPRV DV WUrV SURSULHGDGHV HQXQFLDGDV DFLPD &R"
pDERDHVWUDWpJLDSDUDUHVROYHURMRJRQRPHQRUQ~PHURGH
PHFHPRVSHODSULPHLUDRVGLVFRVHVWmRWRGRVQDKDVWHLQLFLDO
FOLTXHVFRQVLVWHDSHQDVHPHVFROKHUGHVGHRLQtFLRR~QLFRFOL"
TXHGLVSRQtYHOTXHDSDUWLUGDVHJXQGDMRJDGDQmRGHVIDoD
DMRJDGDDQWHULRU
3DUDH[SULPLUGHXPPRGRVLPSOHVXPDHVWUDWpJLDFRPR
PtQLPRQ~PHURGHPRYLPHQWRVQRFDVRGRMRJRGDVWRUUHVGH
+DQyLpFyPRGRWHUGLVFRVDOWHUQDGDPHQWHGHXPDFRUFODUD
HRXWUDHVFXUD'HL[DVHDROHLWRUDYHULÀFDomRGHTXHDPDQHL"
UDPDLVUiSLGDGHFRQFOXLUDWUDQVIHUrQFLDGHXPDKDVWHSDUD
RXWUDFRQVLVWHHPQXQFDS{UXPGLVFRGLUHWDPHQWHVREUHRXWUR
GH WRQDOLGDGH LGrQWLFD ,VWR GHWHUPLQD R PRYLPHQWR D ID]HU
Figura 6
TXDQGRQmRKiKDVWHVYD]LDV3DUDLQFOXLURVFDVRVGHKDVWHV
YD]LDV QD UHJUD LQGLFDGD EDVWDUi LPDJLQDU QR WDEXOHLUREDVH
WUrVGLVFRVYLUWXDLVÀJXUDRVGDVKDVWHVGHSDUWLGDHGHFKH"
JDGDFRPWRQDOLGDGHGLIHUHQWHGDGRGLVFRPDLRUHRGDKDVWH
UHVWDQWHFRPDPHVPDWRQDOLGDGHGRGLVFRPDLRU(QWUHDVSR"
VLo}HVLQGLFDGDVQDÀJXUDIRUDPRPLWLGDVUHVSHWLYDPHQWH
HSRVLo}HVLQWHUPpGLDVQRWRWDOGHGH]RXVHMDHVWmR
PRVWUDGDVVHLVGDVGH]DVVHLV
&RPHVWDVFRQYHQo}HVTXDQWRjVMRJDGDVpPXLWRIiFLOHQ"
FRQWUDUDHVWUDWpJLDyWLPDEDVWDQXQFDGHVID]HUDMRJDGDDQWH"
Figura 7
ATRACTORrJogos isomorfos
05
VHHVyVHFDGDGLVFRLQFOXLQGRR7HVWLYHUVREUHRGLVFRGHQ~"
GHDFOLFDUQDOkPSDGDHYLFHYHUVD(VWHWLSRGHUDFLRFtQLR
PHURLPHGLDWDPHQWHVHJXLQWHSRUWDQWRVHHVyVHDVOkPSDGDV
HVWHQGHVHDRVUHVWDQWHVGLVFRV6XSRQKDPRVTXHQmRpRGLVFR
HVWLYHUHPWRGDVDSDJDGDV4XDQWRjVHJXQGDWRGRVRVGLVFRV
TXHVHPRYHVHUiRGLVFR@HPFLPDGDVRXWUDVKDVWHVTXHIRU
HVWDUHPQXPDKDVWHGLIHUHQWHGDLQLFLDOHTXLYDOHDVyRGLVFR
PDLVSHTXHQRHOHVWrPFRUHVGLIHUHQWHV1mRKDYHUiQHVVDV
7QmRHVWDUVREUHRVHJXLQWHPDLRURTXHSRUVXDYH]HTXLYDOH
GXDVKDVWHVQHQKXPGLVFRPDLVSHTXHQRGRTXHRGLVFR'@SRU
'@
"
DVyHVWDUDOkPSDGD7DFHVD0DVVyKiXPDSRVVLELOLGDGHGH
WDQWRWRGRVHOHVHVWDUmRQDKDVWHGRSULPHLURGLVFRLVWRpVH
REWHUHVWDFRQÀJXUDomRWRGRVRVGLVFRVHVWDUHPQDKDVWHÀQDO
Mйй!йDVOkPSDGDVGHDMйй( HVWDUmRWRGDVDSDJDGDVHPTXDO"
²DTXHODTXHWHPXPGLVFRGHWRQDOLGDGHRSRVWDjGRPDLRUH
TXHUFDVRDOkPSDGDMйй( HVWDUiDFHVD4XDQWRDRGLVFRMй. QmRpRGHRUGHPQй. RXHVWiLPHGLDWDPHQWHSRUEDL[RGRGLVFR@RXpRGRWRSRGD
2EVHUYHVHDLQGDTXHDRORQJRGRMRJRVHPDQWpPDUHSDU"
RXWUDKDVWH1RSULPHLURFDVRDRPRYHURGLVFR@DOkPSDGD
@
WLomRLQLFLDOGDVFRUHVGRVGLVFRVGHFLPDDFRUGRGLVFRPDLV
@SDVVDGHDSDJDGDDDFHVDQRVHJXQGRFDVRSDVVDGHDFHVDD
SHTXHQRHHPFDGDXPDGDVRXWUDVGXDVKDVWHVXPGHFDGD
DSDJDGD(PDPERVRVFDVRVHVVDDomRFRUUHVSRQGHDXPFOL"
FRU$UD]mRpTXHXPPRYLPHQWRSHUPLWLGRPXGDSDUDDFRU
TXHQDOkPSDGD@HVWDQGR
@
Mйй( DFHVDHWRGDVDVDQWHULRUHVDSD"
RSRVWDjGHOHDFRUGRGLVFRQRWRSRGDKDVWHGHRQGHVDLXH
JDGDV (VWD DUJXPHQWDomR SRGH VHU DSUHVHQWDGD HP VHQWLGR
PXGD SDUD D FRU GHOH D FRU GR GLVFR QR WRSR GD KDVWH SDUD
LQYHUVRSDUDTXDOTXHUFOLTXHQXPDOkPSDGDQRFDVRGHKDYHU
RQGHIRL
PXGDQoDGHHVWDGR1DÀJXUDpMй йHR~OWLPRPRYLPHQWR
9HMDPRVDJRUDDWHUFHLUDFRQGLomR2~QLFRGLVFRTXHSRGH
IRL GR GLVFR PDLV SHTXHQR FRUUHVSRQGHQGR D XP FOLTXH QD
HYHQWXDOPHQWHHVWDUHPFLPDGRVHJXQGRpRPDLVSHTXHQR
SULPHLUDOkPSDGDTXHDDFHQGHXSRUWDQWRRGLVFR@YDLSDUD
RXVHMDRSULPHLURHVHQmRHVWLYHUQHQKXPRVHJXQGRVHUi
FLPDGRGLVFRMй. HDOkPSDGD@DSDJDVH2VRXWURVFDVRVGH
R~QLFRGLVFRGHFRUGLIHUHQWHGRSULPHLURTXHHVWiQRFLPRGH
FOLTXHQmRPXGDPRHVWDGRGDVOkPSDGDVFRUUHVSRQGHPDR
XPDKDVWH3RUWDQWRTXDQGRRGLVFRPDLVSHTXHQRVHPRYH
GLVFRMй. RXDGLVFRVTXHQmRHVWmRQRWRSRGDVKDVWHVHQmR
RXYDLSDUDFLPDGRVHJXQGRRXVDLGHFLPDGRVHJXQGR1R
SRGHPSRLVVHUPRYLGRV3RUWDQWRÀFDHVWDEHOHFLGDDHTXL"
SULPHLUR FDVR D SULPHLUD OkPSDGD DSDJDVH QR VHJXQGR
YDOrQFLDRLVRPRUÀVPRHQWUHRVGRLVMRJRVRGDVOkPSDGDV
DFHQGHVH,VWRpTXDOTXHUPRYLPHQWRGRGLVFRFRUUHVSRQ"
HRGDVWRUUHVGH+DQyLPDLVUHVWULWLYR(P>@pSRVVtYHOMRJDU
RVGRLVMRJRVHREVHUYDURLVRPRUÀVPRGHVFULWR
REFERÊNCIAS
>@A##+BCC...;!#"!*#&";+#C2!#CD&%&,E,&2&"-&,C")%"!,;*(>@A##+BCC...;.&5-"!2;*&2C*(-?+5!F)"
>@'A##+BCC...;,+2;+#C&5$2+$!(!,
>@A##+BCC...;!#"!*#&";+#C2!#CD&%&,E,&2&"-&,'
1
Um clique numa lâmpada fá-la mudar de estado se e só se ela for a primeira da fila, ou então se a única lâmpada acesa à sua esquerda for a contígua.
O estado das lâmpadas à direita da lâmpada clicada é, pois, irrelevante. Nas
filas de ambas as figuras seguintes, a 4ª lâmpada muda o seu estado por um
clique e qualquer das duas filas muda de uma das figuras indicadas para a outra:
Figura 8
06
GAZETA DE MATEMÁTICA r169
2
Este problema foi proposto na Final Nacional das XXIX Olimpíadas de
Matemática de 2011 (categoria B −2º dia). Ver [3].