Математиката в билярда :)

[sophos_moros]

Привет на всички!
Ще съм благодарен ако ми помогнете.
Става въпрос за една задача по информатика, в която проблемът е предимно математически. Представете си една правоъгълна маса за билярд с размери a и b. Тези естествени числа принадлежат от 1 до 1,000,000,000 включително. Ако топка започва да се търкаля от връх по направление, сключващо ъгъл 45 градуса със страните на
масата, колко пъти ще се отрази топката от стените на масата, докато
отново се окаже в някой връх?
Дори и да не разбират от информатика, сигурен съм за много хора, че могат да ми помогнат като предложат идея за решаване на проблема.

[Реклама]

[Irrefutable]

Брат, в това няма информатика. Чисто геометрия + модулна аритметика.

Поздрави и бира.

[martosss]

[sophos_moros]

Да от връх тръгва.
Въпросът ми е може ли понякаква формула или друг по-лесен начин да се намери директно отговора, вместо да се проиграва цялата ситуация. Представете си че а=89756467 и b=78664. Аз лично бих намерил отговора много бавно.

[b1ck0]

А замислял ли си се че размерите на масата не са от значение ... ??!?!

Единствено ако a=b, то топката ще влезе право с срещуположния джоб ...

[martosss]

хмм... а замислял ли си си, че ако а=2б и топката тръгва от горния ляв ъгъл, то топката ще влезне в горния десен ъгъл? или ако а=2.5б, я пак помисли, b1ck0, аз не се обадих, защото не знам колко са комбинациите, но не са малко, сигурно си има формула с остатъка а-б , но не се сещам как да я изкарам

[Irrefutable]

а=89756467 и b=78664
Нека C е най-големия общ делител на а и б. C = 1 (89756467 и 78664 са взаимно прости , да не повярваш )
A = a/C = 89756467
B = b/C = 78664
И рикушетите са на брой A + B - 2 = 89835129
Това е в общи линии. Някой ако не го мързи може да прави проверка.

[sophos_moros]

Irrefutable, явно че това е формулата (прoбвах едни примери с по-малки числа). Може ли да обясниш защо е така?
и...
Тази задача към кой дял от математиката спада? Теория на числата ,комбинаторика, нещо друго?

[Irrefutable]

До формулата лесно се стига. Идеята е да се абстрахираш от самото отблъскване на топката от стената. Защото пътуването на топката по x и по y са независими едно от друго.
След като е независимо просто ти трябва пресечна точка. А за да намериш най-малката пресечна точка, просто трябва да имаш взаимно прости числа.

lcm(a,b) (най-малко общо кратно) ти дава пресечната точка. Но за да намериш броят на пресичанията по х и у, делиш на a и на б. Значи търсеният отговор е lcm(a,b)/a + lcm(a,b)/b -2 ( -2 идва от това че финала не го броиш за пресичане)

Обаче ако искаш да си олесниш формулата, по-лесно е да разделиш а и б на gcd(а,б) и да получиш взаимно прости числа, тоест lcm(a,b) = а*б от там формулата ти става a*b/а + а*b/b - 2 = а+b-2

[sophos_moros]

Благодаря за помощта! Разбрах го!

[erejnion]

as a matter of fact, тази задача практически я имаше на последния Power Contest ...
а след като не схванах решението на Irrefutable (браво на sophos_moros), позволете ми да го напиша с мои думи:
нека вместо топката да се отблъсква от стените, да си представим, че тя си върви по права линия, а вместо това ние наслагаме дъската по пътя и в равнината (това сигурно е абстрахирането от отблъскването ). топката минава през точките с координати (x,x), а джобовете попадат в точките с координати (k.a, l.b) -> ще падне в джоба с координати (lcm(a,b),lcm(a,b)) -> ударите ще бъдат lcm(a,b)/a + lcm(a,b)/b - 2 (пресичанията по x и по y са по едиколкоси и последните две не ги броим) ;; а това в кой джоб ще падне е въпрос на четност
Обаче, ако искаш да си Улесниш формулата, ... и Irrefutable го е написал.

... сигурно нямаше нужда от това
... нищо, аз съм си спамър

... това е към ... броене? dunno...

... и още един коментар:: всъщност можеш да направиш почти същото за произволен ъгъл

... последно: по-веселата част от Power Contest бе за подобна задача на дъска с формата на равностранен триъгълник, но аз не бях разпределен на тази част и не помня нищо но пък ще е весело да се проучи ситуацията