Berapa banyak cookie di kotak cookie? - Bintang ubin

19

Dengan musim liburan yang datang, saya memutuskan untuk membuat beberapa bintang kayu manis . Itu menyenangkan (dan hasilnya enak), tetapi kutu buku bagian dalam saya meringis ketika saya meletakkan nampan pertama dari bintang-bintang di dalam kotak dan mereka tidak muat dalam satu lapisan:

masukkan deskripsi gambar di sini

Hampir! Apakah ada cara mereka bisa cocok? Seberapa baik kita bisa memasang bintang? Mengingat bahwa ini adalah bintang berujung enam biasa, kita tentu bisa menggunakan tilings segi enam yang terkenal sebagai perkiraan, seperti:

masukkan deskripsi gambar di sini
Mengacaukan yang ke kanan atas, whoops.

Tetapi apakah ini optimal? Ada banyak ruang di antara ujung-ujungnya.

Untuk pertimbangan ini, mari kita batasi diri kita pada kotak persegi panjang dan bintang berujung enam, reguler, yaitu ada tiga puluh derajat (atau ) antara setiap ujung dan sudut tetangganya. Bintang-bintang ditandai oleh jari-jari dalam dan jari-jari luar : riroπ6riro

masukkan deskripsi gambar di sini
[ sumber ]

Perhatikan bahwa kita memiliki untuk dan hexagram untuk . Saya pikir masuk akal untuk menganggap ini ekstrem (untuk cookie) dan membatasi diri pada rentang di antaranya, yaitu .ri=1ri=32roriri=13rorir0[13,32]

Cookie saya memiliki dan mengabaikan ketidaksempurnaan - saya mencari selera, bukan bentuk untuk sekali!r o25 m mri17mmro25mm

Apa ubin optimal untuk bintang seperti dicirikan di atas? Jika tidak ada ubin terbaik statis, apakah ada algoritma untuk menemukan yang baik secara efisien?

Raphael
sumber
1
Ya, saya tahu: apa yang sudah Anda coba dan di mana Anda terjebak? Ini hanya "masalah" nyata yang lucu yang saya pikir bisa menyenangkan untuk dipikirkan di musim kue, terutama bagi mereka yang pemikir dan bukan tukang roti. Selamat bersenang-senang!
Raphael
4
Agaknya Anda terjebak pada pembekuan. Di dapur. * rimshot *
David Richerby

Jawaban:

15

Biarkan saya menjawab pertanyaan Anda sebagian untuk kasus heksagram.

Anda dapat membuat ubin berikut

masukkan deskripsi gambar di sini

Dengan ini Anda akan mencakup 12/14 = 6/7 dari pesawat (hitung segitiga dalam segiempat putus-putus).

Apakah ini optimal? Saya akan berpikir begitu. Meskipun saya tidak memberikan bukti, saya akan memberikan beberapa argumen. Orang bisa bertanya, seberapa bagus kita bisa mengisi ruang (segitiga) di antara paku runcing. Pada ubin di atas kita isi setengahnya. Bisakah kita berbuat lebih baik?

masukkan deskripsi gambar di sini

sec2(x)23tan(x)+2.

Alur fungsi ini terlihat seperti ini dan menunjukkan bahwa intuisi kita benar.

masukkan deskripsi gambar di sini

A.Schulz
sumber
0

berikut ini tidak ditawarkan sebagai serangan definitif atau spesifik / superior pada masalah yang mungkin tak terduga ini kompleks tetapi sebagai tambahan sudut ilmiah / teoritis / studi umum yang tidak dibahas sejauh ini.

1 st daerah ini umum dikenal / diklasifikasikan sebagai "bin packing" dan ini adalah kasus 2d. ada beberapa bukti terkenal dari matematika yang terkait misalnya kasus 3d penyelidikan Keplers ke pengemasan bola yang merupakan masalah terbuka selama berabad-abad dan "baru-baru ini" diselesaikan dengan bukti komputer oleh Hales. contoh kasus 2d yang digunakan setiap hari di industri adalah untuk mengoptimalkan tata letak chip. jelas ini berbeda dari masalahnya tetapi dapat menunjukkan beberapa kompleksitas dari jenis masalah ini. misalnya sepertinya tidak ada teori yang mensyaratkan / mengindikasikan bahwa kasus 2d akan lebih sederhana daripada kasus 3d. juga perhatikan bahwa batas persegi panjang sederhana tidak selalu membantu menyederhanakan solusi selain katakanlah, batas poligonal.

mungkin ada solusi analitik yang mungkin jika beberapa jenis definisi dasar / skema "ubin biasa" diberikan dalam pernyataan masalah seperti penempatan pada kisi dll. dalam hal ini persamaan kalkulus dapat diturunkan dan optimal yang dapat ditemukan.

kondisi masalah (mungkin berlawanan dengan intuisi) tampaknya tidak mengarah pada solusi optimal analitik. ini mungkin mengejutkan untuk beberapa masalah tetapi sangat mirip dari ubin pesawat diketahui tidak dapat diputuskan (ini adalah hasil yang terkenal bertahun-tahun yang lalu dan ada banyak referensi dan bahkan penelitian yang sedang berlangsung). perbedaan utama antara masalah yang dapat dipecahkan (dipecahkan / analitik) dan masalah yang tidak dapat diputuskan adalah apakah ubin "biasa". masalah di atas mengacu pada "bintang biasa" tetapi tidak merujuk ke "ubin biasa". jawaban lain saat ini mengasumsikan semacam ubin atau urutan biasa, tetapi perhatikan bahwa bahkan mendefinisikan "ubin biasa" bisa sangat rumit secara formal / matematis.

masalah seperti ini umumnya cukup setuju dengan algoritma genetika . algoritma semacam itu dapat menemukan paket "sangat baik" yang tidak mungkin ditingkatkan banyak, dan mungkin beberapa batasan dapat ditempatkan pada optimalitasnya melalui metode yang sangat cerdik (yaitu harus dalam kesalahan kecil persentase optimal), tetapi tidak dapat membuktikan apa pun optimal.

berikut adalah beberapa referensi yang secara umum dapat langsung diterapkan:

ay
sumber
teori serupa lihat juga pengemasan tetrahedron oleh Chang / NYT. dugaan (agak terinspirasi oleh artikel): untuk masalah khusus ini, ada kemasan yang tidak teratur yang lebih unggul daripada yang biasa.
vzn
0

Sementara masalah khusus ini mungkin belum diteliti, pertanyaan seperti itu telah diajukan oleh Laszlo Fejes Toth dan dikenal sebagai masalah pengemasan. Saya sangat merekomendasikan bab ketiga dari buku Pach-Agarwal .

domotorp
sumber
1
Seperti ini, ini bukan jawaban tetapi komentar. Bisakah Anda meringkas isi buku yang dikutip tentang masalah ini dan bagaimana penerapannya di sini?
Raphael