Обыграй Сфинкса логическая головоломка о разрезании лестниц

Вы – расхититель гробниц. Нужно пройти над пропастью по лестнице, охраняемой Сфинксом. Как водится, Сфинкс задает загадку. Решите задачу неверно – и лестница провалится в пропасть, когда вы по ней пойдете.

Условие задачи. Строительными блоками лестницы являются балки с квадратным сечением, соединенные по три таким образом, что срез имеет форму тримино (как у правой фигуры на рисунке). Для каких n можно составить лестницу из таких тройных блоков, если n – число квадратных балок в ее основании? На рисунке приведено поперечное сечение лестницы для n = 8 .

Другими словами, какие лестничнообразные фигуры с основанием из n квадратов можно разрезать нацело на тримино?

Эта задача – пятнадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – алгоритмическую задачу о прыгающих лягушках. Ответ и новая задача будут опубликованы в 14:00 в субботу.

Решение алгоритмической задачи о лягушках

Если вы не решали эту задачу, прежде чем читать приведенный ниже текст, прочитайте условие и попробуйте решить самостоятельно!

Решение. Движение лягушки сводится либо к прыжку через лягушку противоположного вида, либо к переходу лягушки на соседнюю пустую клетку. Таким образом, если мы найдем общее количество прыжков и переходов, мы узнаем общее количество ходов.

Прыжок – единственный способ, которым лягушки противоположного вида могут преодолеть друг друга. Мы сталкивались с этим ранее в предыдущих задачах: получается, что для того, чтобы преодолеть друг друга, им необходимо совершить n 2 прыжков в случае n настоящих и n виртуальных лягушек.

Сдвиг. Рассмотрим далее ситуацию для лягушек одного вида. Мы знаем, что они не могут перепрыгивать друг через друга. Первая лягушка переместится на n + 1 клеток и окажется в ячейке n + 2 , вторая лягушка передвинется на n + 1 клеток до ячейки n + 3 , и т. д. Чтобы оказаться в нужной позиции, вместе все лягушки одного вида должны переместиться на n (n + 1) клеток. Аналогично должны сделать их виртуальные аналоги. То есть все эти реальные и виртуальные земноводные переместятся на 2 n (n + 1) клеток. Поскольку один прыжок охватывает две ячейки, и их n 2 , количество сдвигов должно составить 2n (n + 1) – 2n 2 = 2n .

Алгоритм. Существует два симметричных алгоритма для решения головоломки: один начинается со сдвига крайней к пустой ячейки настоящей лягушки, другой – со сдвига виртуальной. Опишем первый. Алгоритм может быть получен методом грубой силы: его ходы определены однозначно, потому что альтернативные ходы приводят к очевидным тупиковым ситуациям. В частности, когда есть выбор между сдвигом и прыжком, должен быть сделан прыжок.

Ниже приведены алгоритмы для n = 2 и n = 3 соответственно. Настоящие лягушки обозначены T , виртуальные – F .

Решение для n = 2 Решение для n = 3

Головоломка может быть легко обобщена на случай с m и n лягушками разных видов. Общее количество необходимых ходов равно mn + m + n , из которых mn – количество прыжков, а m + n – число сдвигов.

Ответ: для 3 лягушек с каждой стороны достаточно 15 ходов.

Ответ на вопрос со звёздочккой: Для m и n лягушек достаточно mn + m + n ходов.

Как ответили читатели Библиотеки программиста? Сам ответ о числе переходов первым дал пользователь wil4, но без указания решения:

Первым ответ с решением, но с чуть большим числом ходов дал пользователь mr.fantazylight:

Обыграй Сфинкса логическая головоломка о разрезании лестниц

В комментариях к решению задачи мы обсудили, откуда берутся два лишних хода.

Программное решение, находящее алгоритм для любого m и n , реализовал на С++ пользователь krotbsod. Вот пример для m = 3 и n = 5 :

Вы пропустили

AEGIS Algorithms Android Angular Apache Airflow Apache Druid Apache Flink Apache Spark API API Canvas AppSec Architecture Artificial Intelligence Astro Authentication Authorization AutoGPT AWS AWS Aurora AWS Boto3 AWS EC2 AWS Lambda Azure Babylon.js Backend bash Beautiful Soup Bento UI Big Data Binary Tree Browser API Bun Career Cassandra Charts ChatGPT Chrome Extension Clean Code CLI ClickHouse Coding Codux Combine Compose Computer Context Fusion Copilot Cosmo Route CProgramming cron Cryptography CSS CTF Cypress DALL-E Data Analysis Data science Database dbt dbt Cloud deno Design Design Patterns Detekt Development Distributed Systems Django Docker Docker Hub Drizzle DRY DuckDB Express FastAPI Flask Flutter For Beginners Front End Development Game Development GCN GCP Geospatial Git GitHub Actions GitHub Pages Gitlab GMS GoFr Golang Google Google Sheets Google Wire GPT-3 GPT3 Gradio Gradle Grafana Graphic Design GraphQL gRPC Guidance HMS Hotwire HTML Huawei HuggingFace IndexedDB InfoSec Interview iOS Jackknife Java JavaScript Jetpack Compose JSON Kafka Kotlin Kubernetes LangChain Laravel Linux LlaMA LLM localStorage Logging Machine Learning Magento Math Mermaid Micro Frontends Mobile Mobile App Development mondayDB MongoDB Mongoose MySQL Naming NestJS NET NetMock Networks NextJS NLP Node.js Nodejs NoSQL NPM OOP OpenAI OTP Pandas PDF PHP Playwright Plotly Polars PostgreSQL Prefect Productivity Programming Prometheus Puppeteer Pushover Python Pytorch Quarkus Rabbitmq RAG Ramda Raspberry Pi React React Native Reactor Redis REST API Revolut Riverpod RProgramming Ruby Ruby on Rails Rust Scalene SCDB ScyllaDB Selenium Servers Sklearn SLO SnowFlake Snowkase Software Architecture Software Development Solara Solid Spring Boot SQL SQLite Streamlit SudoLang Supabase Swift SwiftUI Tailwind CSS Taipy Terraform Testing Transformers TURN TypeScript Ubuntu UI Design Unix UX UX Design Vim Vite VSCode Vue Web Architecture Web Components Web Development Web Frameworks Web Scraping Web-разработка Webassembly Websocket Whisper Widgets WordPress YAML YouTube Zed Наука о данных Разное Тренды

Как исследовать и визуализировать данные МО для обнаружения объектов на изображениях