tipai packing

sanyojan mein, tipai packing ack tri-ayami grid mein kaee asambaddh tipai khojane kii samasya haye, jahaan ack tipai ack anant polycube haye, grid cubes kaa sangh teen sakaratmak aksh-sanrekhit kiranon key saath ack saajha sheersh key saath.
tiling aur packing tripods aur sambandhit aakaron kii kaee samasyaon koo 1967 mein sherman key dwara taiyar kiya gayaa thaa. stein. stein koo mool roop seey iss samasya key tipai "ardh-paar" kahaa jaataa thaa, aur unhein soloman doubleu dwara stein corner bhee kahaa jaataa thaa. golmol. asambaddh tipai key sangrah koo ack monotonic matricks key roop mein sankshipt roop seey darshaaya jaa sakata haye, ack varg matricks jisaki gair-shoonya pravishtiyaan pratyek pankti aur stambh key saath badhati hain aur jinaki barabar gair-shoonya pravishtiyaan koshikaon key monotonic anukram mein rakhee jaati hain, aur samasya koo "2-samaantaa" naamak ack sangatata sthiti koo santusht karane vaale teen key sett khojane key sandarbh mein bhee taiyar kiya jaa sakata haye, yaa ack uttal bahubhuj mein tribhujon key sangat sett khojane key sandarbh mein bhee.
tripods kii sankhya key liye sabse achchi nichali seema gyaat haye joe apane sheershon koo ack sootra _ 1 grid mein paik curr sakati haye, sootra _ 2 haye, aur sabse achchi oopari seema sootra _ 3 haye, donon badey omega sanketan mein vyakt kiye jaate hain.
samatulya samasyaaen.
tipai samasya key samadhan key sheershon key nirdeshank sootra 4 seey dou-tulaniya trigun hotey hain, jahaan dou trigunon koo dou-tulaniya honey key roop mein paribhaashit kiya jaataa haye yadi cumm seey cumm dou nirdeshank hain jahaan ack trigun dusare seey chhota haye, yaa cumm seey cumm dou nirdeshank jahaan ack trigun dusare seey badaa haye. yeh sthiti yeh sunishchit karati haye kii inn teen prakaron seey paribhaashit tipai mein pratichhedan kiranen naa houn.
prashn kaa ack anya samatulya dou-ayami sanskaran poochata haye kii varg koshikaon kii ack sootra _ 5 sarani (sootra _ 6 seey sootra _ 7 taka anukramit) kii kitni koshikaon koo sootra _ 6 seey sootra _ 7 taka kii sankhyaon dwara iss tarah seey bharaa jaa sakata haye kii pratyek pankti kii gair-khaali koshikaaen aur sarani key pratyek stambh sankhya key anukramon koo sakhti seey badhaaen, aur pratyek moolya sootra _ 10 koo dhaaran karane vaali sthiti sarani key bheetar ack monotonic shrinkhala banaaen. inn gunon key saath ack sarani koo ack monotonic matricks kahaa jaataa haye. sheersh sootra _ 4 key saath asambaddh tipai key sangrah koo sarani koshika sootra _ 13 mein sankhya sootra _ 12 koo rakhkar ack monotonic matricks mein badala jaa sakata haye aur isake vipareet.
samasya ack uttal bahubhuj key sheershon key beach adhik seey adhik trikon khojane key barabar haye, jaise kii kissy bhee dou trikon joe ack sheersh koo saajha karate hain, usa sheersh parr nihit konn naheen hotey hain. yeh tribhuj-ginati kii samasya peater brais dwara utpann kii gaee thee aur tripod packing key liye isaki samaantaa aeronov aur anya dwara dekhi gaee thee.
nichali seemaaen.
formula _ 14 tripods key saath tripod packing samasya kaa samadhan khojana seedha haye. udaaharan key liye, sootra _ 15 key liye, sootra _ 14 triple
sootra _ 17
2-atulaniya hain.
iss saralata mein kaee pahale key sudhaaron key baad, govers aur lambe samay seey cardinality formula _ 2 kii tipai samasya kaa samadhan milaa.
oopari seemaaen.
tipai packing samasya key kissy bhee samadhan seey, koee bhee ack santulit tripakshiya graph praapt curr sakata haye jisake sheersh sootra _ 19 seey sootra _ 20 (teen nirdeshankon mein seey pratyek key liye ack) taka kii sankhyaon kii teen pratiyaan hain, jisamen pratyek tipai key sheersh key nirdeshank key anuroop teen sheershon koo jodane vaale kinaaron kaa ack trikon haye. inn graphon mein koee anya trikon naheen hain (way sthaaniya roop seey raikhik graph hain) kyonki koee bhee anya trikon 2-samaantaa kaa ullanghan karega. isaliye, ruzaa-zemerady samasya key liye gyaat oopari seema dwara (jiska ack sanskaran ack santulit tripakshiya sthaaniya roop seey raikhik graph mein kinaaron key adhikatam ghanatva koo khojane key liye haye), ack sootra _ 1 grid mein paik kiye jaa sakane vaale asambaddh tipai kii adhikatam sankhya sootra _ 22 haye, aur adhik sateek roop seey sootra _ 23 haye. haalaanki tiskin likhate hain kii "maapdandon kaa sakht vishleshan" ack aisee seema kaa utpaadan curr sakata haye joe ack bahupad-ganit kaarak dwara dwighaat seey cumm haye, vaha vivaran kii aapoorti naheen kartaa haye aur uska pramaan haye kii sankhya sootra _ 22 kewal unheen takneekon kaa upayog kartaa haye joe ruzaa-zimereddy samasya key liye gyaat hain, isaliye yeh majboot daavaa ack galati prateet hoti haye.
deane hickerson key ack tark seey pataa chalata haye kii, kyonki tipai sthir ghanatva key saath sthaan koo paik naheen curr sakate hain, yahee uchch aayamon mein anuroop samasyaon key liye sach haye.
chhote udaaharan.
tipai samasya key chhote udaharanon key liye, sateek samadhan gyaat haye. sootra _ 26 key liye, ack sootra _ 1 ghana mein paik kiye jaa sakane vaale tipai kii sankhyaaen hainh
udaaharan key liye, yeh aankada 11 tipai koo darshaata haye jinhen ack sootra _ 27 ghana mein paik kiya jaa sakata haye.
sootra _ 29 key liye crum sootra _ 7 key vishisht monotonic matricks kii sankhya haye

