Математические задачки. Морковкин, скучаем :-)

Так





.

Так давай внимательно посчитать количество бананы в последняя строка//
Сейчас сколько есть в ответ?

.

Сложная задача, предназначенная для сингапурских школьников.

"Альберт и Бернард только что познакомились с Шерил. Они хотят знать, когда у неё день рождения. Шерил предложила им десять возможных дат: 15 мая, 16 мая, 19 мая, 17 июня, 18 июня, 14 июля, 16 июля, 14 августа, 15 августа и 17 августа. Затем Шерил сказала Альберту месяц своего рождения, а Бернарду — день. После этого состоялся диалог.

Альберт: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает.
Бернард: Поначалу я не знал, когда у Шерил день рождения, но знаю теперь.
Альберт: Теперь я тоже знаю, когда у Шерил день рождения.

Когда у Шерил день рождения?"

Лично я понятия не имею (пока) когда у Шерил день рождения, но понял что Бернард смышленый малый!

16 июля день рождения Шерил.

А вот задачка. В последнем чемпионате города Васюки 10 человек сыграли каждый с каждым по 1 партии. После турнира выяснилось что чистое 1 место завоевал гроссмейстер Остап Бендер, а остальные девять разделили места со 2 по 10. Сколько очков набрал великий комбинатор?

9

Расстояние между двумя авто 120 км. Машины начинают двигаться навстречу друг другу, каждая со скоростью 60 км/час. В момент начала движения с одной машины слетает муха и движется в ту же сторону со скоростью 90 км/час. Эта муха долетает до второй машины и тутже летит обратно и так пока машины не храяпнутся. Сколько км налетает муха?

У этой задачи есть очень простое решение арифметикой за 3 класс, но обычно народ решает её очень сложными методами
ответ:

90

муха летает в течении одного часа со скорость 90 км/ч

Ребенок только после толстой подсказки сообразил. Я ему говорю: долго ты еще будешь штаны через голову надевать? Сразу въехал

Вот задача:

Том Сойер красит забор, состоящий из 13 вертикальных дощечек. У него есть 4 краски — красная, желтая, зеленая, синяя. Каждую дощечку он хочет покрасить целиком в один из этих 4-х цветов. Сколько существует способов покрасить забор, если из эстетических соображений Том не хочет, чтобы две подряд дощечки были покрашены в зеленый или две подряд дощечки не были покрашены в синий цвет? Все четыре цвета должны быть использованы.

Фигасе! А две подряд желтые и красные катят?

Катят. Запрещены только две подряд синие либо зеленые.

Где C – количество красок; d – количество досок; p – количество красок, которые не должны повторяться. (d>=C>=p)

Есть идея: индукция по числу досок в заборе. Но конечно тут хитрости при переходе в индукционном шаге от N к N+1. Надо учитывать все конфигурации в N, а не только допустимые по условию (не все цвета использованы). И еще отделять те конфигурации, где последняя доска красная/желтая от тех где синяя и тех где зеленая. То есть конфигурация в N описывается набором из К неиспользованных цветов, и цветом последней доски. Индукция ведет подсчет количества конфигураций в каждом классе. Ответом будет число конфигураций в допустимом классе.

А вот еще как можно, правда численно (в стиле Монте Карло). Отбросим все эстетические условия, получится ответ 4 в 13ой степени. Теперь будем генерировать произвольную конфигурацию и проверять удовлетворяет она эстетическим условиям или нет. Ясно, что сходимость наступит довольно быстро.

Проверьте формулу при С=d=4

—- добавлено: 5 окт 2016, опубликовано: 5 окт 2016 —-

Я примерно так и решил. Только индукция там не работает; индукцией хорошо проверять формулы, но не выводить. Там ближе к динамической системе

Ну да, сходится:
For 2^1 simulations probability = 0
For 2^2 simulations probability = 0.25
For 2^3 simulations probability = 0.375
For 2^4 simulations probability = 0.25
For 2^5 simulations probability = 0.3125
For 2^6 simulations probability = 0.265625
For 2^7 simulations probability = 0.273438
For 2^8 simulations probability = 0.234375
For 2^9 simulations probability = 0.226562
For 2^10 simulations probability = 0.231445
For 2^11 simulations probability = 0.234863
For 2^12 simulations probability = 0.234375
For 2^13 simulations probability = 0.231934
For 2^14 simulations probability = 0.227234
For 2^15 simulations probability = 0.227997
For 2^16 simulations probability = 0.228516
For 2^17 simulations probability = 0.226608
For 2^18 simulations probability = 0.225533
For 2^19 simulations probability = 0.225914
For 2^20 simulations probability = 0.225557
For 2^21 simulations probability = 0.225644
For 2^22 simulations probability = 0.225912
For 2^23 simulations probability = 0.226091
For 2^24 simulations probability = 0.226174
For 2^25 simulations probability = 0.226166
For 2^26 simulations probability = 0.226164
For 2^27 simulations probability = 0.226166
For 2^28 simulations probability = 0.226155
For 2^29 simulations probability = 0.226167
For 2^30 simulations probability = 0.226168

Реально 0.226164281368256

Грубая оценка - 4*3.5**12, т.е. отношение ко всем вариантам (7/8)**12 - чуть больше 20%. Или нужна большая точность?

Банальное 4*3^12 не прокатывает? лень думать, если тут ошибка, скорее всего есть, если все предлагают более сложное

Почему 3? Коэффициент немного больше 3.5, т.к. после красного-желтого может идти любой цвет (4), после зеленого-синего - без идентичного (3). Частота красного-желтого немного выше, поэтому от 3.5 вверх, начиная от третьей доски. Однако для грубой оценки это не столь существенно. Чтобы провести точный подсчет потребуется минимум пол-часа, а оценить можно за минуту: (7/8)**3 = 2/3, (2/3)**4 = 1/5. Вполне достаточно для Тома Сойера.

P.S. Я исхожу из того, что забор не замкнут, т.е. первая доска не граничит с 13-ой. Иначе просто > 3.5**13.

Да, спасибо, уже тогда почти сразу понял. где ошибся, но не было возможности сразу исправить или дополнить сообщение.
В табличном редакторе посчитал, опять же, если ничего не напутал. Для 13-той дощечки получилось 16 413 466 "расстановок". ( для каждого из этапов 4- 14- 50- 178- 634- 2258- 8042- 28642- 102010- 363314- 1293962- 4608514- 16 413 466 ).
4в 13-ой будет 67108864 т.е. примерно 0,24458
"Рекурсивное" соотношение (зависимость эн от эн минус первой) вроде бы понял и смогу объяснить "словами", но пока объяснить просто и кратко, а тем более формулой не смог... ( табличным редактором руками "решается" за 5 минут)

Понял как объяснить просто, кратко и общую формулу по методу, которым я решал (правильно или нет решал-уже не перепроверял "набело" логику решения).
Пусть П -число возможных вариантов на каждом этапе., а н-номер "этапа " и П (н+1) -Пэ от эн тогда будет число вариантов покраски по условию на этапе эн плюс 1 (следующий за эн).
П(н) = П(н-1)*3+П(н-2)*2.

Объяснение такое. Возможность покрасить зависит от "своего цвета и чужого" . Если предыдущие доски оканчиваются чужим цветом, то мы смело можем красить любым из оставшихся трех. И первое слагаемое-это число предыдущих вариантов, покрашенных чужим цветом (предыдущий вариант дополняется дощечкой любым из 3 оставшихся чужих цветов.) Осталось прибавить варианты, где мы красим свой цвет последующим своим. Этих подвариантов 2 (красный и желтый), поэтому умножаем на 2. А сколько своих цветов будет оканчиваться на каждом этапе? Если правильно определил, то как раз ровно столько, сколько было вариантов на 2 этапа раньше. Потому что второе слагаемое в каждом случае будет дополнять "желтые и красные" окончания предыдущего этапа до ровно количеству вариантов предыдущего предыдущему.

если опять нигде не запутался

Где-то запутались, ответ другой. Поясните, что такой "свой" цвет и что "чужой".

А где учитывается что должны быть использованы все цвета?

Наиболее ясный путь это в каждый момент N следить за набором классов и числом вариантов в каждом из них. Переход от N к N+1 это ход. Возможных ходов всегда 4 по числу цветов. Ход переводит вариант из класса в класс или оставляет в том же классе. Класс описывается набором неиспользованных цветов и цветом последней доски (с исключением когда последняя доска желтая или красная это один класс). Например, для N = 2 вариант, где первая доска Зеленая, вторая Красная принадлежит классу M = {Ж,С ; К} Тут неиспользованы желтый и синий; последняя доска красная(желтая).

Допустим следующий ход Ж. Он переводит класс M в класс M' = {С ; К} в N = 3. Главная идея здесь, что если мы знаем число элементов в M в момент N = 2, и все ходы вида L -> M', которые переводят произвольный класс L в тот же самый М', то мы знаем число элементов в M' в N = 3.

Так мы ползем с классами, увеличивая N пока не доползем до N = 13. Нам нужны все эти классы потому что в любой момент класс может стать допустимым, то есть вида { ; X}, все цвета использованы. И именно такие классы с разными X нам нужны в ответе.

То есть это направленный граф с градуировкой по N. Если N считать временем, то действительно получается динамическая система с конечным числом состояний (классов) и конечным числом переходов (4).

Мне пришлось ввести 12 классов, и динамика тогда определяется матрицей 12х12.
Решение системы - линейная комбинация степеней (по номеру шага) собственных значений этой матрицы.

У меня тоже получается 12 классов, если не учитывать отдельно цвет последней доски, и тогда чуть сложнее вычисления при переходе. Или 26 классов, если учитывать и тогда вычисления чуть проще. Но не настолько чтобы плодить лишние классы.

Какие классы, какая динамика? Матрица 2-2-2-1, собственные числа - решение уравнения L*L-3*L-2=0, или, в самом деле, рекурентная формула П(н) = П(н-1)*3+П(н-2)*2. Можно смотреть как на формулу для красного цвета, тогда К1=1, К2=4, ищем К14. Или сразу П1=4, П2=14, ищем П13.

(3/4)**12 < (1/3)**3 < 4%
Это прикладная задача, в которой важно получить ответ с приемлемой погрешностью - собственно, в примерном расчете погрешностей и выборе средств решения и состоит задание. Если потрачено более 10 минут или тем более привлечен калькулятор, то тест провален. Полагаю, Тома Сойера вполне должен удовлетворить ответ, что его эстетические пристрастия сократили число раскрасок в 4-5 раз.

Не увидел ограничения, что нужно использовать все цвета (решение вспоминал по памяти и или выпало, или просто его не заметил).
Я решал комбинаторную задачу на размещение с повторением (частичным). Если все еще правильно понимаю условие задачи, то для учета "использовать все цвета" для моего решения достаточно отнять все случаи (возможности) с одним, двумя и тремя цветами ??!
И эти случаи элементарные, кроме трех цветов, где встречаются синий и зеленый с дополнительным цветом (хотя и это по тому же рекурсивному приему будет , видимо П(н)= П(н-1)*2+П(н-2) для каждого из случаев. которых всего 2-сзж и сзк.)
А цвет-"свой-чужой", то это близко/равнозначно Вашему переходу в следующий класс. Если цвет чужой, то мы смело умножаем на 3 и -главное-выделяем неизменяемую рекурсивную составляющую , с которой легко работать . Если чужой -то уже есть различия в несочетаемости синего с зеленым.