* Врабчетата и клоните
Публикувано на 26 май 2010 в раздел Математика.
В един форум се появи интересна математическа задача, която са я давали на интервю за работа в спедиторска фирма. Стори ми се много лесна и затова дадох поредица от изключително грешни и срамни решения (за което "добронамерени" хора ми се подиграваха) преди да задълбая сериозно в нея. Ясно - поизложих се много. Ето я и задачата:
Задача: На клоните на едно дърво кацнали по равен брой врабчета, а едно си летяло наоколо. След малко всичките врабчета се прегрупирали така, че единият клон останал празен, а по останалите клони отново имало равен брой врабчета и нямало нито едно летящо. Колко са клоните и колко са врабчетата?
Решение: Ако x е броят на врабчетата, а p броя на клоните, то горното условие се свежда до следното: намерете кои цели положителни числа x>0 и p>1 са такива, че x се дели без остатък на (p-1) и (x-1) се дели без остатък на p .
Както казах след поредица от неуспешни и смешни опити, все пак стигнах до следните заключения:
При нечетно число клони p имаме x=(p-1)(p-1+kp) врабчета, за всяко k=0,1,2,3,4...
При четно число клони p имаме x=p(p-2+k(p-1))+1 врабчета, за всяко k=0,1,2,3,4...
Докажете или оборете, че това са решения. Ако са решения, то докажете или оборете, че са единствените решения.
има частен случай:
когато кацат по едно на клон, за едно врабче няма клон
когато кацат по две на клон, за един клон няма врабчета.
Как се вписва в твоето решение?
този случай е с единствено решение.
За колко клона и колко врабчета говорим?
две независими уравнения с две неизвестни.
Просто няма място за параметър K
Вижте пак във форума, намериха се и елементарни решения на ниво гимназия, не е нужна диофанова математика.
Иво - Не виждам как ще съставиш две уравнения - няма данни за толкова. Уравнението е едно и е с две неизвестни. Аз реших задачата разглеждайки четност и нечетност на клоните. Евентуално с повече финес могат да се обединят в едно.
K е просто променлива според която се намират различните решения. Тя не е неизвестно.
Форумец - Частните решения не са интересни. Търси се пълно решение на задачата.
а -брой врабчета
б - брой клони
когато кацат по едно на клон, за едно врабче няма клон:
а = б + 1
когато кацат по две на клон, за един клон няма врабчета:
2(б - 1) = а
=> б+1 = 2б - 2
Нещо не схващам какво искаш да обясниш. Кой каза, че кацат по едно на клон? Може да кацат и по две на клон... и по n на клон...
Нека дам един конкретен пример. Имаш 5 клона и 56 врабчета. Преди прегрупирането е имало по 11 врабчета на клон (5*11 = 55) и 56тото е хвърчало. След прегрупирането е имало по 14 врабчета на клон (4 клона по 14 врабчета = 56 врабчета) и един клон е бил свободен.
Надявам се, че този частен случай изяснява проблема...
това е частен случай на твоята задача и той не зависи от параметър. Как си го обясняваш?
Какъв параметър бе човек? Параметрите в задачата са два "брой клони" и "брой врабчета". Те са зависими един от друг. Взимайки конкретен брой клони имаш безброй много решения за брой врабчета, но все пак пряко зависими от броя клони - именно формулата, която съм дал. Взимайки конкретно k при фиксиран брой клони имаш частно решение. Взимайки всички възможни k при фиксиран брой клони, намираш клас от решения. Взимайки всички възможни броеве клони и всички съответни техни подрешения (чрез промяна на k) ти намираш всички възможни решения въобще.
Фактически и за четните и за нечетните в крайна сметка се получава едно и също след разкриване на скобите.
Ще ви дам един мой вариант, макар че може да не е верен. Най малкият брой врабчета на определен брой клони е: x=(p-1)**2
За всеки по голям брой врабчета k=1,2,3,4... се прибавя p(p-1), или цялата формула:
x=(p-1)**2+kp(p-1).
С уговорката, че за един клон няма решение, а за два клона важат всички нечетни числа >1.
Тези формули ги изведох емпирично, не съм ги доказвал и не съм сигурен дали са верни. Затова ако има грешка моля да ме извините.
Какво означава "**2"?
Исках да напиша на втора степен(на квадрат). Съжалявам че не го уточних. Значи смятам по тази формула, че врабчетата при три клона са съответно 4,10, 16, 22... Най малкия брой (p-1)**2=(3-1)**2=4, стъпката е шест: p(p-1)=3(3-1)=6
1 1 1 1 - врабчета
| | | - клони
2 2 0 - врабчета
3 3 3 1
| | |
5 5 0
и т.н.
За четири клонки 9, 21 33, 45...
x=(p-1)**2+kp(p-1)=(4-1)**2+k*4(4-1)
което означава най малък брой 9 и стъпка 12
напр. за k=2: 9+2*12=33
8 8 8 8 1
| | | |
11 11 11 0
за 5 клона - 16, 36, 56, 76...
за 6 клона - 25, 55, 85...
и т.н.
Към ivo_isa
Твоят въпрос е частен случай, ето къде се вписва:
x=(p-1)**2+kp(p-1)
За p=3 и k=0 --> x=(3-1)**2+0*3(3-1)
x=4
Значи три клона и четири врабчета. Първо трите са кацнали и едното хвърчи, след прегрупирането са кацнали 2х2 и единия клон е свободен.
А на моя клон веднъж кацнаха 15 врабчета, а други 3 не можаха и летяха наоколо. Нека да призная, че едно от 15-те стоеше на един крак.
Задачата е логическа и е в учебника по математика за 4 клас. Отговора е:
Клоните са 5 а врабчетата 16 .
Даниел Петров - това е само един частен случай и НЕ е пълно решение на задачата. За 4-ти клас може да получиш 6. Ако си учил повече, имаш слаб 2.