• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 14:31
CEST 20:31
KST 03:31
  • 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
[ASL19] Finals Recap: Standing Tall9HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Flash Announces Hiatus From ASL63Weekly Cups (June 23-29): Reynor in world title form?13FEL Cracov 2025 (July 27) - $8000 live event22Esports World Cup 2025 - Final Player Roster16Weekly Cups (June 16-22): Clem strikes back1
StarCraft 2
General
Program: SC2 / XSplit / OBS Scene Switcher The SCII GOAT: A statistical Evaluation Statistics for vetoed/disliked maps Weekly Cups (June 23-29): Reynor in world title form? PiG Sty Festival #5: Playoffs Preview + Groups Recap
Tourneys
FEL Cracov 2025 (July 27) - $8000 live event RSL: Revival, a new crowdfunded tournament series Sparkling Tuna Cup - Weekly Open Tournament WardiTV Mondays Korean Starcraft League Week 77
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma Mutation # 477 Slow and Steady
Brood War
General
Flash Announces Hiatus From ASL BW General Discussion Player “Jedi” cheat on CSL SC uni coach streams logging into betting site Practice Partners (Official)
Tourneys
The Casual Games of the Week Thread CSL Xiamen International Invitational [BSL20] Grand Finals - Sunday 20:00 CET [Megathread] Daily Proleagues
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Path of Exile Stormgate/Frost Giant Megathread Nintendo Switch Thread What do you want from future RTS games? Beyond All Reason
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 Russo-Ukrainian War Thread Summer Games Done Quick 2025! Trading/Investing Thread Things Aren’t Peaceful in Palestine
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
Formula 1 Discussion 2024 - 2025 Football Thread NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
Blogs
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
Blog #2
tankgirl
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 584 users

The Big Programming Thread - Page 860

Forum Index > General Forum
Post a Reply
Prev 1 858 859 860 861 862 1031 Next
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.
Nesserev
Profile Blog Joined January 2011
Belgium2760 Posts
March 10 2017 19:52 GMT
#17181
--- Nuked ---
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2017-03-10 20:40:39
March 10 2017 20:16 GMT
#17182
Haha, I'm glad people enjoyed that question. It was memorable to me because I was annoyed about the time limit as well when I was doing it the first time and didn't finish.

In hindsight I think it's a good question: it has a lot of pretty straightforward coding sections like palindrome, lends itself well to breaking down into parts, has lots of areas for optimizations, and then the short time limit adds a nice intensity given I think most people could find an okay solution in 30 minutes.

This takes me 4 minutes to code, but I have the advantage of knowing the question and my previous attempt :p

mfw trying to read slmw's O(n) solution... lol

+ Show Spoiler +

bool is_palindrome(string s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
}

int longest_palindrome(vector<string> text) {
int max_length = 0;
for (string s: text) {
for (int i = 0; i < s.length(); i++) {
for (int j = s.length() - 1; j > i && (j - i + 1) > max_length; j--) {
if (s[i] == s[j] && is_palindrome(s.substr(i, j - i + 1))) {
max_length = max(max_length, j - i + 1);
}
}
}
}
return max_length;
}

int main() {
vector<string> text = {
"carracecar",
"aabbaa",
"aabbbabab"
};

for (string s: text) {
cout << is_palindrome(s) << endl;
}

cout << longest_palindrome(text) << endl;

return 0;
}
There is no one like you in the universe.
Fwmeh
Profile Joined April 2008
1286 Posts
March 11 2017 09:39 GMT
#17183
I'm not sure that I understand the complexity analysis of that proposed O(n) solution. I would treat a for-loop with a nested while bound by the length (and half the length is still bound by the length) of the string as O(n^2).

Best I could do, certainly more than 5 minutes. https://ideone.com/M4tVmS. O(n^2), but reasonably good constants.
A parser for things is a function from strings to lists of pairs of things and strings
meatpudding
Profile Joined March 2011
Australia520 Posts
March 11 2017 09:55 GMT
#17184
I guess it's really O(nm) where n is the word length and m is the palindrome length.
Be excellent to each other.
slmw
Profile Blog Joined October 2010
Finland233 Posts
Last Edited: 2017-03-11 12:54:34
March 11 2017 12:53 GMT
#17185
The algorithm in question is Manacher's algorithm. The idea is that we maintain the currently rightmost palindrome, which means that we can look up some of the answers from the left side of the current palindrome since it's simply a mirrored case. The while loop will fail on the first iteration any time we are inside a larger palindrome and don't update the rightmost palindrome. If we need to expand the current palindrome, we update the rightmost palindrome. That means on each iteration we either move the current rightmost palindrome further or do an O(1) copying of a value. The rightmost palindrome can move only at most N times, so the whole algorithm is O(N) per string.

If you try every substring (N^2) in a string and check if it is a palindrome you get an O(N^3) algorithm. That is what Fwmeh's and many others' solution is doing. If you try every midpoint and expand until it is no longer a palindrome, you get an O(N^2) algorithm. This is what travis's solution was doing for odd palindromes.
Manit0u
Profile Blog Joined August 2004
Poland17243 Posts
Last Edited: 2017-03-13 14:14:27
March 13 2017 14:08 GMT
#17186
Does anyone here know any resources where I can dig up some imposition calculation algorithms for printing presses?

I've got new assignment today: rewrite old PHP library as new Ruby gem. Sounds simple enough, but then there's a couple of problems:

  • no documentation
  • no tests
  • entire library is a single class that's 4k lines long (basically no empty lines)
  • at the top of class the error reporting is being disabled (which doesn't bode well)
  • there's plenty of magic arbitrary numbers and overall code readability is on par with assembler
  • loops nested 6 deep with other control statements spread throughout
  • 2k lines of configuration
  • large arrays in global variables, which are being manipulated in different ways by different functions (reversed, reversed with reindexing, values moved around and changed etc. etc.)


After nearly 7 hours of sifting through it I simply gave up trying to understand what's going on in there and I'm looking to simply write this shit from scratch. So, if you know of any resources or ready libraries (any language) that deal with this kind of stuff, please help...

+ Show Spoiler [sample] +


function build_collect_placement_array($sect=1){
$count_pairs = count($this->grid_build_used[$sect]);
$inc = 1;
for ($x = 1; $x <= $count_pairs; $x++){ // build an array for each of the two pair numbering patterns
if ($inc > 0) {
if ($x == 1) {
$add_a = 1; // first instance
} else {
$add_a = $arr_b[$x-1] + $inc;
}
if ($add_a==$count_pairs){
$add_b = $add_a;
$inc = -2;
} else {
$add_b = $add_a + $inc;
}
if (($add_b==$count_pairs)&&($add_a!=$count_pairs)){
$inc = 0;
}
} else {
if ($inc == 0) {
$add_b = $arr_b[$x-1];
$inc = -1;
} elseif ($inc == -2) {
$add_b = $arr_b[$x-1] + $inc;
} else {
$add_b = $arr_a[$x-1] + $inc;
}
if ($inc == -2) {
$add_a = $add_b + 1;
} else {
$add_a = $add_b + $inc;
}
}
$arr_a[$x] = $add_a;
$arr_b[$x] = $add_b;
}
$place_arr_a = $arr_a;
$place_arr_b = $arr_b;

$keep_count=1;
for ($x = 1; $x <= 4; $x++){ // loop for each column
for ($y = 1; $y <= $count_pairs; $y++){ // create array for pair placement
$final_pr_arr[$y+($count_pairs*2*($x-1))] = $place_arr_a[$y];
$final_pr_arr[$y+($count_pairs*2*($x-1))+$count_pairs] = $place_arr_b[$y];
}
if (((($count_pairs % 2)==0)||($x==1)||($x==3))&&(($this->grid_cols != 2)||((($this->grid_cols == 2)&&($count_pairs % 2)==0)))){
$temp_arr = $place_arr_a;
$place_arr_a = $place_arr_b;
$place_arr_b = $temp_arr;
}
for ($y = 1; $y <= 2; $y++){ //
for ($z = 1; $z <= 2; $z++){ // build the sub-grid pattern
$inc=0;
if (($count_pairs % 2)==1){ // there is an odd number of pairs
if (($x == 1)||($x == 4)){
if (($y == 1)&&($z == 2)){
$inc=1;
}
if (($y == 2)&&($z == 1)){
$inc=1;
}
}
if (($x == 2)||($x == 3)){
if (($y == 1)&&($z == 1)){
$inc=1;
}
if (($y == 2)&&($z == 2)){
$inc=1;
}
}
if (($this->grid_cols == 2)&&($x == 2)){ // different sub-grid pattern for 4-up
if ((($y == 1)&&($z == 2))||(($y == 2)&&($z == 1))){
$inc=1;
} else {
$inc=0;
}
}
}
for ($a = 1; $a <= (ceil($count_pairs/2)-$inc); $a++){ // create array for sub-grid placement
$final_sg_arr[$keep_count] = $x*2-(2-$z);
$keep_count++;
}
}
}
}
if(is_array($final_pr_arr)) {
foreach ($final_pr_arr as $key => $final_pr_val){
$final_arr[$key]["pair"] = $final_pr_val;
$final_arr[$key]["subgrid"] = $final_sg_arr[$key];
}
ksort($final_arr);
return $final_arr;
}
return null;
}


One of my favorites:

list($rows, $columns) = array($columns, $rows);

Time is precious. Waste it wisely.
BluzMan
Profile Blog Joined April 2006
Russian Federation4235 Posts
Last Edited: 2017-03-13 15:56:57
March 13 2017 15:54 GMT
#17187
On March 13 2017 23:08 Manit0u wrote:
Does anyone here know any resources where I can dig up some imposition calculation algorithms for printing presses?

I've got new assignment today: rewrite old PHP library as new Ruby gem. Sounds simple enough, but then there's a couple of problems:

  • no documentation
  • no tests
  • entire library is a single class that's 4k lines long (basically no empty lines)
  • at the top of class the error reporting is being disabled (which doesn't bode well)
  • there's plenty of magic arbitrary numbers and overall code readability is on par with assembler
  • loops nested 6 deep with other control statements spread throughout
  • 2k lines of configuration
  • large arrays in global variables, which are being manipulated in different ways by different functions (reversed, reversed with reindexing, values moved around and changed etc. etc.)


After nearly 7 hours of sifting through it I simply gave up trying to understand what's going on in there and I'm looking to simply write this shit from scratch. So, if you know of any resources or ready libraries (any language) that deal with this kind of stuff, please help...

+ Show Spoiler [sample] +


function build_collect_placement_array($sect=1){
$count_pairs = count($this->grid_build_used[$sect];
$inc = 1;
for ($x = 1; $x <= $count_pairs; $x++){ // build an array for each of the two pair numbering patterns
if ($inc > 0) {
if ($x == 1) {
$add_a = 1; // first instance
} else {
$add_a = $arr_b[$x-1] + $inc;
}
if ($add_a==$count_pairs){
$add_b = $add_a;
$inc = -2;
} else {
$add_b = $add_a + $inc;
}
if (($add_b==$count_pairs)&&($add_a!=$count_pairs)){
$inc = 0;
}
} else {
if ($inc == 0) {
$add_b = $arr_b[$x-1];
$inc = -1;
} elseif ($inc == -2) {
$add_b = $arr_b[$x-1] + $inc;
} else {
$add_b = $arr_a[$x-1] + $inc;
}
if ($inc == -2) {
$add_a = $add_b + 1;
} else {
$add_a = $add_b + $inc;
}
}
$arr_a[$x] = $add_a;
$arr_b[$x] = $add_b;
}
$place_arr_a = $arr_a;
$place_arr_b = $arr_b;

$keep_count=1;
for ($x = 1; $x <= 4; $x++){ // loop for each column
for ($y = 1; $y <= $count_pairs; $y++){ // create array for pair placement
$final_pr_arr[$y+($count_pairs*2*($x-1))] = $place_arr_a[$y];
$final_pr_arr[$y+($count_pairs*2*($x-1))+$count_pairs] = $place_arr_b[$y];
}
if (((($count_pairs % 2)==0)||($x==1)||($x==3))&&(($this->grid_cols != 2)||((($this->grid_cols == 2)&&($count_pairs % 2)==0)))){
$temp_arr = $place_arr_a;
$place_arr_a = $place_arr_b;
$place_arr_b = $temp_arr;
}
for ($y = 1; $y <= 2; $y++){ //
for ($z = 1; $z <= 2; $z++){ // build the sub-grid pattern
$inc=0;
if (($count_pairs % 2)==1){ // there is an odd number of pairs
if (($x == 1)||($x == 4)){
if (($y == 1)&&($z == 2)){
$inc=1;
}
if (($y == 2)&&($z == 1)){
$inc=1;
}
}
if (($x == 2)||($x == 3)){
if (($y == 1)&&($z == 1)){
$inc=1;
}
if (($y == 2)&&($z == 2)){
$inc=1;
}
}
if (($this->grid_cols == 2)&&($x == 2)){ // different sub-grid pattern for 4-up
if ((($y == 1)&&($z == 2))||(($y == 2)&&($z == 1))){
$inc=1;
} else {
$inc=0;
}
}
}
for ($a = 1; $a <= (ceil($count_pairs/2)-$inc); $a++){ // create array for sub-grid placement
$final_sg_arr[$keep_count] = $x*2-(2-$z);
$keep_count++;
}
}
}
}
if(is_array($final_pr_arr)) {
foreach ($final_pr_arr as $key => $final_pr_val){
$final_arr[$key]["pair"] = $final_pr_val;
$final_arr[$key]["subgrid"] = $final_sg_arr[$key];
}
ksort($final_arr);
return $final_arr;
}
return null;
}


One of my favorites:

list($rows, $columns) = array($columns, $rows);


Looks like regular production code to me, also pretty well-formed. At least this doesn't have 20 global declarations at the start of each function like our code did.

Based on the sample you provided I would definitely try to reuse it, deep control structure nesting does not necessarily imply redundancy, it might just be that the field is actually that difficult. In that was the case, rewriting it from scratch would be a pretty stupid thing to do. Maybe start with writing tests for the parts you understand and slowly increase the coverage as your understanding grows? Could also refactor obvious subroutines into functions, etc.

Throwing working code away and rewriting from scratch is almost never a good idea.

One of my favorites:

list($rows, $columns) = array($columns, $rows);


That is a pretty creative way to do a swap one-liner Can you implement cpp-style swap with references in php? Don't remember the exact way they work.
You want 20 good men, but you need a bad pussy.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-03-13 17:27:20
March 13 2017 17:26 GMT
#17188
I am studying for my discrete math midterm. Here is a question that an old exam asks:

Prove:
If a, b, c and d are consecutive integers, 4 | abcd.

*please note that this is under the heading "formal proofs"


So my answer is:

+ Show Spoiler +

Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd.


Here is what the answer key says:

+ Show Spoiler +

Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd.


So I guess my question is, does my answer suffice for a "formal" proof?
Also this question is dumb.
Acrofales
Profile Joined August 2010
Spain17971 Posts
March 13 2017 17:50 GMT
#17189
I think your answer is fine. Whether your teacher agrees i don't know...
tofucake
Profile Blog Joined October 2009
Hyrule19031 Posts
March 13 2017 17:51 GMT
#17190
Depends on how strict the grader is. Your answer is correct, but it's not a mathematical proof.
Liquipediaasante sana squash banana
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
March 13 2017 18:05 GMT
#17191
So technically to make it a mathematical proof I would need to do what? State step one mathematically and then prove the other steps by mathematically manipulating what I start with?
Biolunar
Profile Joined February 2012
Germany224 Posts
March 13 2017 18:15 GMT
#17192
There is no such thing as a “mathematical proof”. A proof is a proof, if it is correct independent of how it was proven.
Same goes of following example: ℕ = { n ∈ ℤ | n ≥ 0 } is not more “mathematically” than ℕ = { n ∈ ℤ | n is greater or equal to zero }, although the former is more formal.
What is best? To crush the Zerg, see them driven before you, and hear the lamentations of the Protoss.
Manit0u
Profile Blog Joined August 2004
Poland17243 Posts
March 13 2017 21:35 GMT
#17193
On March 14 2017 00:54 BluzMan wrote:
Show nested quote +
On March 13 2017 23:08 Manit0u wrote:
Does anyone here know any resources where I can dig up some imposition calculation algorithms for printing presses?

I've got new assignment today: rewrite old PHP library as new Ruby gem. Sounds simple enough, but then there's a couple of problems:

  • no documentation
  • no tests
  • entire library is a single class that's 4k lines long (basically no empty lines)
  • at the top of class the error reporting is being disabled (which doesn't bode well)
  • there's plenty of magic arbitrary numbers and overall code readability is on par with assembler
  • loops nested 6 deep with other control statements spread throughout
  • 2k lines of configuration
  • large arrays in global variables, which are being manipulated in different ways by different functions (reversed, reversed with reindexing, values moved around and changed etc. etc.)


After nearly 7 hours of sifting through it I simply gave up trying to understand what's going on in there and I'm looking to simply write this shit from scratch. So, if you know of any resources or ready libraries (any language) that deal with this kind of stuff, please help...

+ Show Spoiler [sample] +


function build_collect_placement_array($sect=1){
$count_pairs = count($this->grid_build_used[$sect];
$inc = 1;
for ($x = 1; $x <= $count_pairs; $x++){ // build an array for each of the two pair numbering patterns
if ($inc > 0) {
if ($x == 1) {
$add_a = 1; // first instance
} else {
$add_a = $arr_b[$x-1] + $inc;
}
if ($add_a==$count_pairs){
$add_b = $add_a;
$inc = -2;
} else {
$add_b = $add_a + $inc;
}
if (($add_b==$count_pairs)&&($add_a!=$count_pairs)){
$inc = 0;
}
} else {
if ($inc == 0) {
$add_b = $arr_b[$x-1];
$inc = -1;
} elseif ($inc == -2) {
$add_b = $arr_b[$x-1] + $inc;
} else {
$add_b = $arr_a[$x-1] + $inc;
}
if ($inc == -2) {
$add_a = $add_b + 1;
} else {
$add_a = $add_b + $inc;
}
}
$arr_a[$x] = $add_a;
$arr_b[$x] = $add_b;
}
$place_arr_a = $arr_a;
$place_arr_b = $arr_b;

$keep_count=1;
for ($x = 1; $x <= 4; $x++){ // loop for each column
for ($y = 1; $y <= $count_pairs; $y++){ // create array for pair placement
$final_pr_arr[$y+($count_pairs*2*($x-1))] = $place_arr_a[$y];
$final_pr_arr[$y+($count_pairs*2*($x-1))+$count_pairs] = $place_arr_b[$y];
}
if (((($count_pairs % 2)==0)||($x==1)||($x==3))&&(($this->grid_cols != 2)||((($this->grid_cols == 2)&&($count_pairs % 2)==0)))){
$temp_arr = $place_arr_a;
$place_arr_a = $place_arr_b;
$place_arr_b = $temp_arr;
}
for ($y = 1; $y <= 2; $y++){ //
for ($z = 1; $z <= 2; $z++){ // build the sub-grid pattern
$inc=0;
if (($count_pairs % 2)==1){ // there is an odd number of pairs
if (($x == 1)||($x == 4)){
if (($y == 1)&&($z == 2)){
$inc=1;
}
if (($y == 2)&&($z == 1)){
$inc=1;
}
}
if (($x == 2)||($x == 3)){
if (($y == 1)&&($z == 1)){
$inc=1;
}
if (($y == 2)&&($z == 2)){
$inc=1;
}
}
if (($this->grid_cols == 2)&&($x == 2)){ // different sub-grid pattern for 4-up
if ((($y == 1)&&($z == 2))||(($y == 2)&&($z == 1))){
$inc=1;
} else {
$inc=0;
}
}
}
for ($a = 1; $a <= (ceil($count_pairs/2)-$inc); $a++){ // create array for sub-grid placement
$final_sg_arr[$keep_count] = $x*2-(2-$z);
$keep_count++;
}
}
}
}
if(is_array($final_pr_arr)) {
foreach ($final_pr_arr as $key => $final_pr_val){
$final_arr[$key]["pair"] = $final_pr_val;
$final_arr[$key]["subgrid"] = $final_sg_arr[$key];
}
ksort($final_arr);
return $final_arr;
}
return null;
}


One of my favorites:

list($rows, $columns) = array($columns, $rows);


Looks like regular production code to me, also pretty well-formed. At least this doesn't have 20 global declarations at the start of each function like our code did.

Based on the sample you provided I would definitely try to reuse it, deep control structure nesting does not necessarily imply redundancy, it might just be that the field is actually that difficult. In that was the case, rewriting it from scratch would be a pretty stupid thing to do. Maybe start with writing tests for the parts you understand and slowly increase the coverage as your understanding grows? Could also refactor obvious subroutines into functions, etc.

Throwing working code away and rewriting from scratch is almost never a good idea.

Show nested quote +
One of my favorites:

list($rows, $columns) = array($columns, $rows);


That is a pretty creative way to do a swap one-liner Can you implement cpp-style swap with references in php? Don't remember the exact way they work.


It doesn't have 20 global declarations at each function. It has 60 at the top of the file though. Swap one-liner is clever, but it comes out of the blue and is buried deep in other logic (also with functions that span several hundred lines it's easy to miss).

I have to pretty much rewrite it anyway since I have to do it in another language. I've started with various utility functions around the code, but it's hard to implement some of the larger methods since no documentation or anything and magic numbers are bad (also, pi with 5 digit precision jumped at me out of nowhere, no explanation why 5 digits or how important it is...). I've been reading some books from 1895 on imposition, also some Rockwell patents I found on Google. It's damn complicated stuff
Time is precious. Waste it wisely.
Liebig
Profile Joined August 2010
France738 Posts
March 13 2017 21:44 GMT
#17194
On March 14 2017 02:26 travis wrote:
I am studying for my discrete math midterm. Here is a question that an old exam asks:

Prove:
If a, b, c and d are consecutive integers, 4 | abcd.

*please note that this is under the heading "formal proofs"


So my answer is:

+ Show Spoiler +

Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd.


Here is what the answer key says:

+ Show Spoiler +

Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd.


So I guess my question is, does my answer suffice for a "formal" proof?
Also this question is dumb.

I think it's fine, but I would play it safe if it was in the first few questions of the exam and just answer like that

We can assume without loss of generality that b=a+1, c=a+2, d=a+3.
If a=0[4] then a*b*c*d is clearly a multiple of 4
If a=1[4] then d=0[4] and etc

Atreides
Profile Joined October 2010
United States2393 Posts
March 13 2017 21:51 GMT
#17195
On March 14 2017 02:26 travis wrote:
I am studying for my discrete math midterm. Here is a question that an old exam asks:

Prove:
If a, b, c and d are consecutive integers, 4 | abcd.

*please note that this is under the heading "formal proofs"


So my answer is:

+ Show Spoiler +

Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd.


Here is what the answer key says:

+ Show Spoiler +

Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd.


So I guess my question is, does my answer suffice for a "formal" proof?
Also this question is dumb.


Every math professor in the world here is just looking for you to say there is two even numbers bla bla bla. It's ez to formalize.

Jumping straight to divisible by four is obviously doable but slightly harder to formalize. For a question like that the entire thing is formalizing something intuitively obvious so I can't imagine any prof giving full credit for your answer.
Hanh
Profile Joined June 2016
146 Posts
Last Edited: 2017-03-14 01:26:41
March 14 2017 01:10 GMT
#17196
On March 14 2017 03:05 travis wrote:
So technically to make it a mathematical proof I would need to do what? State step one mathematically and then prove the other steps by mathematically manipulating what I start with?


You can only use theorems and axioms that were given to you during your class, so I wouldn't call your answer a formal proof.

Edit:
1. Use the canonical injection to go from N to Z/4Z.
2. By definition, you get 4 different equivalent classes of Z/4Z.
3. Z/4Z has cardinality 4. Therefore one of the classes must be 0.
4. the product is 0
5. Therefore the product is a multiple of 4.
Prillan
Profile Joined August 2011
Sweden350 Posts
March 14 2017 18:33 GMT
#17197
On March 14 2017 03:05 travis wrote:
So technically to make it a mathematical proof I would need to do what? State step one mathematically and then prove the other steps by mathematically manipulating what I start with?

You need to state why the things you do are true. Ask "why?" until you reach an already proved result.
To get you started:
Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4.

Why?
TheBB's sidekick, aligulac.com | "Reality is frequently inaccurate." - Douglas Adams
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2017-03-15 02:10:03
March 14 2017 22:49 GMT
#17198
To add onto everyone's answers, I believe the problem is you're not rigorous enough with your terminology. A formal proof has a certain structure because the structure makes reasoning very clear. In your answer, you've skipped those structures, but the proof is still mostly comprehensible because the domain is pretty straight-forward. But it's likely that the purpose of these exercises is to teach you these concepts in preparation for later proofs - eventually having the concepts translate to programming logic - so skipping these structures kind of misses the point of the lesson.

Now to go over your answer. Correct me if I am wrong, but "multiple" and "factor" are not words in the theorems you've been taught. They are obvious mathematical definitions and results of the theorems, and maybe part of some related, unpresented corollary due to those definitions, but they essentially aren't part of your set of premises. The goal of these exercises is to have you conceptualize how to infer the result, given the premises. Using these "unrelated" concepts and jumping from result to result is what is I meant by not being rigorous.


> Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. (1)

Is this true? It looks like it's true, but how do I prove that? Is it so trivially true that it's unnecessary to show (1*n = n)? Is this the result of some theorem that I know (n|a-b => a === b mod n)? This result is intuitive, in that it's easy enough to convince yourself that this must be true, but how do you show that in writing?

> Therefore 4 can be factored from a*b*c*d. (2)

What did factored come from and what factored mean? Are you saying that "multiple of n" implies "factor out by n"?

> Therefore 4|abcd. (3)

Are you saying that "factor n from x" implies "n | x"?


I think you'd have to enumerate all the cases in (1) to show a proof of it.


Suppose a,b,c,d are consecutive numbers.
Any 4 consecutive numbers (a,b,c,d) must contain 1 number which is a multiple of 4.
<show that this is true>
Without loss of generality, suppose a is divisible by 4.
Therefore there exists n such that a = 4n. (2)
Therefore there exists n such that abcd = 4nbcd.
If x == nbcd, then abcd = 4x.
From definitions, a | b iff a*n = b.
Therefore 4 | abcd. (3)
There is no one like you in the universe.
netherh
Profile Blog Joined November 2011
United Kingdom333 Posts
March 15 2017 04:29 GMT
#17199
On March 15 2017 07:49 Blisse wrote:
Suppose a,b,c,d are consecutive numbers.
Any 4 consecutive numbers (a,b,c,d) must contain 1 number which is a multiple of 4.
<show that this is true>
Without loss of generality, suppose a is divisible by 4.
Therefore there exists n such that a = 4n. (2)
Therefore there exists n such that abcd = 4nbcd.
If x == nbcd, then abcd = 4x.
From definitions, a | b iff a*n = b.
Therefore 4 | abcd. (3)


Probably dumb questions:

What does the line in 4 | abcd mean?
What does "without loss of generality" mean, and why do you use it there?
tofucake
Profile Blog Joined October 2009
Hyrule19031 Posts
March 15 2017 04:35 GMT
#17200
4 | abcd means "4 divides abcd"
Liquipediaasante sana squash banana
Prev 1 858 859 860 861 862 1031 Next
Please log in or register to reply.
Live Events Refresh
BSL: ProLeague
18:00
Grand Finals - bo9
Dewalt vs Bonyth
ZZZero.O284
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
mouzHeroMarine 758
BRAT_OK 130
MindelVK 36
StarCraft: Brood War
Bisu 900
EffOrt 425
Mini 307
ZZZero.O 284
Soma 258
Hyuk 176
TY 114
ToSsGirL 69
Terrorterran 15
HiyA 13
[ Show more ]
LuMiX 5
Stormgate
BeoMulf171
NightEnD11
Dota 2
qojqva2993
League of Legends
Grubby2996
Dendi2110
Counter-Strike
fl0m1627
Super Smash Bros
Mew2King140
Chillindude43
Westballz26
Heroes of the Storm
Khaldor867
Liquid`Hasu520
Other Games
Gorgc3091
FrodaN2805
B2W.Neo730
mouzStarbuck297
KnowMe115
elazer88
Organizations
Other Games
gamesdonequick41245
EGCTV1698
StarCraft 2
angryscii 21
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 19 non-featured ]
StarCraft 2
• HeavenSC 30
• Adnapsc2 26
• maralekos13
• IndyKCrew
• sooper7s
• AfreecaTV YouTube
• Migwel
• intothetv
• LaughNgamezSOOP
• Kozan
StarCraft: Brood War
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• C_a_k_e 4274
• Ler159
League of Legends
• masondota2559
Other Games
• imaqtpie2047
• Shiphtur676
• WagamamaTV378
Upcoming Events
Wardi Open
16h 29m
Monday Night Weeklies
21h 29m
Replay Cast
1d 5h
Sparkling Tuna Cup
1d 15h
WardiTV European League
1d 21h
MaNa vs sebesdes
Mixu vs Fjant
ByuN vs HeRoMaRinE
ShoWTimE vs goblin
Gerald vs Babymarine
Krystianer vs YoungYakov
PiGosaur Monday
2 days
The PondCast
2 days
WardiTV European League
2 days
Jumy vs NightPhoenix
Percival vs Nicoract
ArT vs HiGhDrA
MaxPax vs Harstem
Scarlett vs Shameless
SKillous vs uThermal
Replay Cast
3 days
RSL Revival
3 days
ByuN vs SHIN
Clem vs Reynor
[ Show More ]
Replay Cast
4 days
RSL Revival
4 days
Classic vs Cure
FEL
4 days
RSL Revival
5 days
FEL
5 days
FEL
5 days
Sparkling Tuna Cup
6 days
RSL Revival
6 days
FEL
6 days
Liquipedia Results

Completed

BSL 2v2 Season 3
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL Season 20
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
CSL Xiamen Invitational
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
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
IEM Cologne 2025
FISSURE Playground #1
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.