• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 06:37
CEST 12:37
KST 19:37
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Tournament Spotlight: FEL Cracow 20257Power Rank - Esports World Cup 202576RSL Season 1 - Final Week9[ASL19] Finals Recap: Standing Tall15HomeStory Cup 27 - Info & Preview18
Community News
Google Play ASL (Season 20) Announced22BSL Team Wars - Bonyth, Dewalt, Hawk & Sziky teams10Weekly Cups (July 14-20): Final Check-up0Esports World Cup 2025 - Brackets Revealed19Weekly Cups (July 7-13): Classic continues to roll8
StarCraft 2
General
Tournament Spotlight: FEL Cracow 2025 #1: Maru - Greatest Players of All Time I offer completely free coaching services Power Rank - Esports World Cup 2025 What tournaments are world championships?
Tourneys
FEL Cracov 2025 (July 27) - $10,000 live event Esports World Cup 2025 $25,000 Streamerzone StarCraft Pro Series announced $5,000 WardiTV Summer Championship 2025 WardiTV Mondays
Strategy
How did i lose this ZvP, whats the proper response
Custom Maps
External Content
Mutation #239 Bad Weather Mutation # 483 Kill Bot Wars Mutation # 482 Wheel of Misfortune Mutation # 481 Fear and Lava
Brood War
General
Google Play ASL (Season 20) Announced [Update] ShieldBattery: 2025 Redesign Dewalt's Show Matches in China BGH Auto Balance -> http://bghmmr.eu/ BW General Discussion
Tourneys
[Megathread] Daily Proleagues [BSL20] Non-Korean Championship 4x BSL + 4x China CSL Xiamen International Invitational [CSLPRO] It's CSLAN Season! - Last Chance
Strategy
Simple Questions, Simple Answers [G] Mineral Boosting Does 1 second matter in StarCraft?
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Total Annihilation Server - TAForever [MMORPG] Tree of Savior (Successor of Ragnarok) Path of Exile
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread UK Politics Mega-thread Stop Killing Games - European Citizens Initiative Things Aren’t Peaceful in Palestine Russo-Ukrainian War Thread
Fan Clubs
INnoVation Fan Club SKT1 Classic Fan Club!
Media & Entertainment
[\m/] Heavy Metal Thread Anime Discussion Thread Movie Discussion! [Manga] One Piece Korean Music Discussion
Sports
2024 - 2025 Football Thread Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023 NBA General Discussion
World Cup 2022
Tech Support
Installation of Windows 10 suck at "just a moment" Computer Build, Upgrade & Buying Resource Thread
TL Community
TeamLiquid Team Shirt On Sale The Automated Ban List
Blogs
Ping To Win? Pings And Their…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Eight Anniversary as a TL…
Mizenhauer
Customize Sidebar...

Website Feedback

Closed Threads



Active: 755 users

Math Question?

Blogs > Salv
Post a Reply
Normal
Salv
Profile Blog Joined December 2007
Canada3083 Posts
January 29 2008 04:25 GMT
#1
Got an exam tomorrow morning, in 9hours to be exact ^^, I know I know how to do this, but I can't remember how haha. It's permutations, anyone good at math who could help me out i'l give you a gold star?

OK, question reads:

Sung (nice name btw) is 5blocks east and 4 blocks south of her friend's home. How Mmany different routes are possible if she walks only west or north?

*****
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
Last Edited: 2008-01-29 04:34:12
January 29 2008 04:28 GMT
#2
Pretty sure it has to do with the Catalan numbers. I'll go look.

Err, I guess not.

My noob stab at it:

The path will always be 9 blocks long (displacement is 5 + 4). There will be only 2 choices at most for each step (N or W?). Therefore, an upper limit will be 2^9 routes.

However, at the 4 spots South of Sung's friend's house, there is only 1 choice (go North), and same with the 5 spots East of the house (go West).

Dunno how to account for those.
Compilers are like boyfriends, you miss a period and they go crazy on you.
Salv
Profile Blog Joined December 2007
Canada3083 Posts
January 29 2008 04:31 GMT
#3
Thanks, best I came up with is that Sung needs to walk 5 blocks north and 4 blocks west, it is a must. That's it :S
Salv
Profile Blog Joined December 2007
Canada3083 Posts
January 29 2008 04:36 GMT
#4
I was thinking it was 9factorial divided by 5factorial times 4factorial?

Not sure ;S
ShaLLoW[baY]
Profile Blog Joined January 2007
Canada12499 Posts
Last Edited: 2008-01-29 04:45:04
January 29 2008 04:40 GMT
#5
I'm not sure how to explain it, but it's a Pascal's Triangle variation I think? I suck though, so don't quote me on that. I think it ends up being 126.

1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

I think that's how pascal's triangle goes?
ALEXISONFIRE ARE FUCKING BACK (sAviOr for life)
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
Last Edited: 2008-01-29 04:59:28
January 29 2008 04:44 GMT
#6
erroneous reasoning removed for anti-clutter and embarrassment.
Compilers are like boyfriends, you miss a period and they go crazy on you.
Salv
Profile Blog Joined December 2007
Canada3083 Posts
January 29 2008 04:49 GMT
#7
Well, I was thinking that there is nine ways (5norths, 4wests) and you need all nine of them to complete the trip. But the order you put the wests in doesn't matter, neither do the norths, they are simply norths. So 9! is the answer, but we have to takeout the number of times that would account for west(1) and west(2) being counted as two seperate routes if they reversed position.

It is hard to explain, but I am fairly certain this is correct? Any verification?
fusionsdf
Profile Blog Joined June 2006
Canada15390 Posts
January 29 2008 04:49 GMT
#8
hahaha
I remember this problem.

If you cant figure it out, draw out a grid and list the various paths. Theres a pattern, but I forget how it goes. but if you do the diagram it should be obvious
SKT_Best: "I actually chose Protoss because it was so hard for me to defeat Protoss as a Terran. When I first started Brood War, my main race was Terran."
Salv
Profile Blog Joined December 2007
Canada3083 Posts
January 29 2008 04:49 GMT
#9
On January 29 2008 13:40 ShaLLoW[baY] wrote:
I'm not sure how to explain it, but it's a Pascal's Triangle variation I think? I suck though, so don't quote me on that. I think it ends up being 126.

1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

I think that's how pascal's triangle goes?


I think I remember the answer actually being 126 :O, could you explain this further?
ShaLLoW[baY]
Profile Blog Joined January 2007
Canada12499 Posts
Last Edited: 2008-01-29 04:55:56
January 29 2008 04:53 GMT
#10
[image loading]

You start by placing a 1 next to each intersection at the bottom and right sides as there is only one possible way to reach each of those squares.

You then add the numbers on either side of the intersection to get how many possible ways there are to reach that intersection. (bit confusing, look at how I did 1 + 1 = 2 for the bottom right, then 2 + 1 = 3 for the one above it, cont. until you reach the end)

Man I'm bad at explaining things :p

Obviously you start at the bottom right, and only add upwards and leftwards as you can only walk west and north.
ALEXISONFIRE ARE FUCKING BACK (sAviOr for life)
imDerek
Profile Blog Joined August 2007
United States1944 Posts
January 29 2008 04:55 GMT
#11
Hi,

the method I would use is called block-walking. so consider a coordinate system where (0,0) is where you start from and (5,4) is your ending location. the south direction is set to the +y direction for convinience. since the person can only walk east or south, the calculation is nice.

observe that there is only 1 way to walk from (0,0) -> (1,0) and only 1 way to walk from (0,0) -> (0,1).

now note that you can only go to (1,1) from either (0,1) or (1,0). and since there is only 1 way to get to (0,1) and 1 way to get to (1,0), there is a total of 1+1=2 ways to get to (1,1).

in general, the number of ways to get to (m,n) = number of ways to get to (m-1,n) + number of ways to get to (m, n-1). So this is a recursion. just make a 4x5 grid and do it real quick, and you should get 126.
Least favorite progamers: Leta, Zero, Mind, Shine, free, really <-- newly added
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
January 29 2008 04:56 GMT
#12
Awesome visualization. The 1-6 and 1-5 for the bottom row and rightmost column are obvious. It's then obvious that for every other cell, the number of ways to get there is the number of ways to get to the cell to the East, plus the number of cells to the South. Which happens to be Pascal's triangle.
Compilers are like boyfriends, you miss a period and they go crazy on you.
ShaLLoW[baY]
Profile Blog Joined January 2007
Canada12499 Posts
January 29 2008 04:57 GMT
#13
Yay! I know what I'm talking about for once! <3
ALEXISONFIRE ARE FUCKING BACK (sAviOr for life)
Salv
Profile Blog Joined December 2007
Canada3083 Posts
January 29 2008 04:58 GMT
#14
Wow, nice guys, thanks for the help, I have two great methods to do this question .

Mad props to you both! :D
imDerek
Profile Blog Joined August 2007
United States1944 Posts
January 29 2008 05:01 GMT
#15
the pascal's triangle goes like this

let x be the vector <0,1> and y be the vector <1,0>. you will need 5 y's and 4 x's to get to the point (5,4) and you can arrange them any way you like. so the answer is precisely 9! / (5!*4!).
Least favorite progamers: Leta, Zero, Mind, Shine, free, really <-- newly added
FieryBalrog
Profile Blog Joined July 2007
United States1381 Posts
January 29 2008 05:18 GMT
#16
Add up the number of blocks total. In this case its 9. Go to the 9th power row (10th row, since it starts at 0th power) of the Pascal's triangle. Find the middle number, or the pair of middle numbers. That number is the number of ways to get there.

So yea its 126.
I will eat you alive
Day[9]
Profile Blog Joined April 2003
United States7366 Posts
January 29 2008 05:25 GMT
#17
i can explain this VERY VERY VERY easily. this is a simple combinatorics problem:

you can view your path as a series of W (west) and N (north) moves. For example, a legit enumeration of a path would be " W W W N N W W N N ". Or, we could go "N N N N W W W W W ". We are happy with both because (in the end) there are 5 west moves total and 4 north moves total. So, lets count the total number of enumerated paths!

Since we have NINE TOTAL MOVES, we can simply CHOOSE when to take our FIVE WEST MOVES and the north moves are fixed. For example, if we decided to go "W W W _ _ W W _ _ " we know that all the underscores MUST be north moves (as we have performed all our west moves). Therefore, the total number of unique paths is (9 choose 5) = 9! / (4!5!). (if you didn't know the binomial coefficient (9 choose 5) is the 5th element on the 9th row of pascals triangle).

tada!

god damn i'm good
Whenever I encounter some little hitch, or some of my orbs get out of orbit, nothing pleases me so much as to make the crooked straight and crush down uneven places. www.day9.tv
ShaLLoW[baY]
Profile Blog Joined January 2007
Canada12499 Posts
January 29 2008 05:25 GMT
#18
Pff, my drawing is sexier.
+ Show Spoiler +
<3
ALEXISONFIRE ARE FUCKING BACK (sAviOr for life)
Day[9]
Profile Blog Joined April 2003
United States7366 Posts
January 29 2008 05:26 GMT
#19
my solution is way better than everyone else's yucky brute force or induction (EWW INDUCTION)
Whenever I encounter some little hitch, or some of my orbs get out of orbit, nothing pleases me so much as to make the crooked straight and crush down uneven places. www.day9.tv
ShaLLoW[baY]
Profile Blog Joined January 2007
Canada12499 Posts
January 29 2008 05:29 GMT
#20
On January 29 2008 13:36 Salv wrote:
I was thinking it was 9factorial divided by 5factorial times 4factorial?

Not sure ;S


I just realized that you had it right from the very beginning O_o
ALEXISONFIRE ARE FUCKING BACK (sAviOr for life)
GeneralStan
Profile Blog Joined August 2007
United States4789 Posts
January 29 2008 05:36 GMT
#21
I like the drawing shallow. I see exactly how it relates to Pascal's triangle now!
¯\_(ツ)_/¯
Saracen
Profile Blog Joined December 2007
United States5139 Posts
January 29 2008 05:37 GMT
#22
day9 ftw
Day[9]
Profile Blog Joined April 2003
United States7366 Posts
January 29 2008 06:46 GMT
#23
On January 29 2008 13:28 BottleAbuser wrote:
Pretty sure it has to do with the Catalan numbers. I'll go look.


if sung was disallowed from ever having more north moves than west moves, then yeah it would relate to the catalan numbers.

woooo
Whenever I encounter some little hitch, or some of my orbs get out of orbit, nothing pleases me so much as to make the crooked straight and crush down uneven places. www.day9.tv
Slithe
Profile Blog Joined February 2007
United States985 Posts
Last Edited: 2008-01-29 07:05:48
January 29 2008 07:04 GMT
#24
Day[9]'s solution is the best way to do it. However, I must disagree with his dislike of induction. Induction is awesome.

BTW Day[9], if you think you've got the skills, you should take a crack at the problems in my blog.
Day[9]
Profile Blog Joined April 2003
United States7366 Posts
January 29 2008 08:39 GMT
#25
i dislike induction because it provides no intuition into the problem.

induction is INSANELY powerful and can provide a REALLY easy way of cracking some extremely difficult problems. however, its such a boring mechanical process.

i like pure combinatorics 8]
Whenever I encounter some little hitch, or some of my orbs get out of orbit, nothing pleases me so much as to make the crooked straight and crush down uneven places. www.day9.tv
Polemarch
Profile Joined August 2005
Canada1564 Posts
January 29 2008 08:54 GMT
#26
day wins in solution elegance and attitude
I BELIEVE IN CAPITAL LETTER PUNISHMENT!!!!!
ShaLLoW[baY]
Profile Blog Joined January 2007
Canada12499 Posts
January 29 2008 23:15 GMT
#27
Screw you, I drew a picture.
ALEXISONFIRE ARE FUCKING BACK (sAviOr for life)
Normal
Please log in or register to reply.
Live Events Refresh
FEL
09:00
Cracow 2025
MaNa vs ElazerLIVE!
Spirit vs Gerald
Clem vs TBD
uThermal vs TBD
Reynor vs TBD
Lambo vs TBD
RotterdaM970
ComeBackTV 968
IndyStarCraft 449
CranKy Ducklings145
Rex122
3DClanTV 115
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RotterdaM 970
IndyStarCraft 449
Rex 122
ProTech57
StarCraft: Brood War
Horang2 11339
Hyuk 3630
Hyun 1025
firebathero 758
Larva 660
Barracks 642
Mini 601
BeSt 491
EffOrt 273
Stork 136
[ Show more ]
Noble 97
Last 97
sorry 81
ZerO 70
Soulkey 56
Free 53
zelot 48
scan(afreeca) 32
Shinee 32
soO 24
NaDa 19
Sacsri 17
Sharp 17
Movie 14
ajuk12(nOOB) 9
yabsab 7
sSak 5
Bale 5
Dota 2
XcaliburYe740
Counter-Strike
Stewie2K908
shoxiejesuss595
Heroes of the Storm
Khaldor258
Other Games
gofns13884
Beastyqt591
SortOf82
DeMusliM23
ZerO(Twitch)16
Organizations
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 14 non-featured ]
StarCraft 2
• Berry_CruncH318
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• C_a_k_e 305
• WagamamaTV259
• lizZardDota2228
Upcoming Events
BSL20 Non-Korean Champi…
3h 23m
BSL20 Non-Korean Champi…
7h 23m
Bonyth vs Zhanhun
Dewalt vs Mihu
Hawk vs Sziky
Sziky vs QiaoGege
Mihu vs Hawk
Zhanhun vs Dewalt
Fengzi vs Bonyth
Sparkling Tuna Cup
1d 23h
WardiTV European League
2 days
Online Event
2 days
uThermal 2v2 Circuit
3 days
The PondCast
3 days
Replay Cast
4 days
Korean StarCraft League
5 days
CranKy Ducklings
5 days
[ Show More ]
Sparkling Tuna Cup
6 days
Liquipedia Results

Completed

CSLPRO Last Chance 2025
Esports World Cup 2025
Murky Cup #2

Ongoing

Copa Latinoamericana 4
Jiahua Invitational
BSL 20 Non-Korean Championship
BSL 20 Team Wars
FEL Cracov 2025
CC Div. A S7
Underdog Cup #2
IEM Cologne 2025
FISSURE Playground #1
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25

Upcoming

ASL Season 20: Qualifier #1
ASL Season 20: Qualifier #2
ASL Season 20
CSLPRO Chat StarLAN 3
BSL Season 21
RSL Revival: Season 2
Maestros of the Game
SEL Season 2 Championship
WardiTV Summer 2025
uThermal 2v2 Main Event
HCC Europe
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.